首页 > ACM题库 > HDU-杭电 > HDU 4625-JZPTREE-动态规划-[解题报告]HOJ
2015
09-17

HDU 4625-JZPTREE-动态规划-[解题报告]HOJ

JZPTREE

问题描述 :

There is a tree,there is a life.Can you solve this problem about tree?
Here we have a tree which has n vertices.
We define dist(u, v) as the number of edges on the path from u to v.
And for each vertices u , define Eu =Endless Spin
Give you the tree and k.
Print Ei for every vertices(from 1 to n).(mod 10007 for convenience).

输入:

The first line contains integer T(1  T  5),denote the number of the test cases.
For each test cases,the first line contains two integers n,k(1<=n<=50000, 1<=k<=500).
Then next n-1 lines,each lines contains two integer a,b(1<=a, b<=n),denote there is an edge between a, b.

输出:

The first line contains integer T(1  T  5),denote the number of the test cases.
For each test cases,the first line contains two integers n,k(1<=n<=50000, 1<=k<=500).
Then next n-1 lines,each lines contains two integer a,b(1<=a, b<=n),denote there is an edge between a, b.

样例输入:

1
5 3
1 2
2 3
3 4
4 5

样例输出:

100
37
18
37
100
Hint
Thank oimaster for this problem :).

JZPTREE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 5e4 + 10;
const int maxk = 5e2 + 10;
const int mod = 10007;
typedef long long LL;

struct edge {
  int v, to;
};
vector<edge> E;
int L[maxn];
void graph_init()
{
  E.clear();
  memset(L, -1, sizeof(L));
}
void graph_add(int u, int v)
{
  edge t = {v, L[u]};
  L[u] = E.size();
  E.push_back(t);
}

int s[maxk][maxk];  // stirling
int f[maxk];        // factorial
int c[maxk][maxk];  // pascal

void init()
{
  s[0][0] = f[0] = c[0][0] = 1;
  for (int i = 1; i < maxk; i++) {
    f[i] = f[i-1] * i % mod;
    c[i][0] = 1;
    for (int j = 1; j < maxk; j++) {
      s[i][j] = (j * s[i-1][j] % mod + s[i-1][j-1]) % mod;
      c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
    }
  }
}

int n, k;

int d[maxn][maxk];
void dp_son(int u = 0, int p = -1)
{
  memset(d[u], 0, sizeof(d[u]));
  for (int i = L[u]; i != -1; i = E[i].to)
    if (i != p) {
      int v = E[i].v;
      dp_son(v, i^1);
      for (int j = 0; j <= k; j++)
        d[u][j] = (d[u][j] + d[v][j] + (j? d[v][j-1]: 0) + c[1][j]) % mod;
    }
}
int tmp[maxk];
void dp_father(int u = 0, int p = -1)
{
  if (p != -1) {
    int v = E[p].v;
    memcpy(tmp, d[v], sizeof(d[v]));
    for (int j = 0; j <= k; j++)
      tmp[j] = (tmp[j] - (d[u][j] + (j? d[u][j-1]: 0) + c[1][j]) % mod + mod) % mod;
    for (int j = 0; j <= k; j++)
      d[u][j] = (d[u][j] + tmp[j] + (j? tmp[j-1]: 0) + c[1][j]) % mod;
  }
  for (int i = L[u]; i != -1; i = E[i].to)
    if (i != p) dp_father(E[i].v, i^1);
}

int main()
{
  init();
  int T;
  scanf("%d", &T);
  for ( ; T--; ) {
    graph_init();
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n-1; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      u--, v--;
      graph_add(u, v);
      graph_add(v, u);
    }
    dp_son();
    dp_father();
    for (int u = 0; u < n; u++) {
      int sum = 0;
      for (int i = 0; i <= k; i++)
        sum = (sum + s[k][i]*f[i]%mod*d[u][i]%mod) % mod;
      printf("%d\n", sum);
    }
  }
  return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dwylkz/article/details/9749827