2015
09-17

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 =
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 :).


#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));
}
{
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--;
}
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;
}


1. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

2. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

3. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

4. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

5. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

6. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

7. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把

8. 咳咳，让这里湖南大湘西的人来告诉你。第一种是凉粉~~它是用凉粉加开水搅拌调和出来的凉粉，夏天的时候做好了放在冰箱，吃的时候那点红糖水。入口即化，跟喝冰糖水一样。第二种也叫凉粉，确切的说应该是凉拌粉。对，一般的粉不是都会加热汤加臊子嘛，这种粉没有汤，就是把