题目描述
给出一棵n个点 (1 <= N <= 100,000)的树，每个点上有C_i头牛，问每个点k步(1 <= K <= 20)范围内各有多少头牛。
输入输出格式
输入格式：
Line 1: Two space-separated integers, N and K.
Lines 2..N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly connected by a trail.
- Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)
输出格式：
- Lines 1..N: Line i should contain the value of M(i).
输入输出样例
输入样例#1：
6 2
5 1
3 6
2 4
2 1
3 2
1
2
3
4
5
6
输出样例#1：
15
21
16
10
8
11
说明
There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2). Field i has C(i) = i cows.
Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.
分析：
树形DP。dalao们都说这题很水，然而窝树形DP弱爆了QAQ只敢写了个暴力还写炸...
f[i][j]表示从i点往周围走j步的点权和。
计算过程中先把子树符合要求的f[i][j]加进来，再把i的父亲中符合要求的权值加到f[i][j]里并减去重复值。
AC代码：
1 #include
2 #include
3 #include
4 #include
5
6 const int MAXN = 100003;
7
8 inline void read(int &x)
9 {
10 char ch = getchar(),c = ch;x = 0;
11 while(ch <'0' || ch > '9') c = ch,ch = getchar();
12 while(ch <= '9' && ch >= '0') x = (x<<1)+(x<<3)+ch-'0',ch = getchar();
13 if(c == '-') x = -x;
14 }
15
16 int dp[MAXN][22];
17 //dp[i][j]表示从i往子树走j步的最大权值和
18 int n,k,f,t,cnt;
19 int head[MAXN],vis[MAXN],val[MAXN];
20
21 struct Edge
22 {
23 int f,t,nxt;
24 }e[MAXN<<1];
25
26 void insert(int f,int t)
27 {
28 e[++cnt].f = f,e[cnt].t = t;
29 e[cnt].nxt = head[f],head[f] = cnt;
30 }
31
32 void dfs(int u)
33 {
34 vis[u] = 1;
35 for(int i = 0;i <= k;++ i)
36 dp[u][i] = val[u];
37 for(int i = head[u];i;i = e[i].nxt)
38 {
39 int t = e[i].t;
40 if(vis[t]) continue;
41 dfs(t);
42 for(int j = 1;j <= k;++ j)
43 dp[u][j] += dp[t][j-1];
44 }
45 }
46
47 void calc(int u)
48 {
49 vis[u] = 1;
50 for(int i = head[u];i;i = e[i].nxt)
51 {
52 int t = e[i].t;
53 if(vis[t]) continue;
54 for(int j = k;j >= 2;-- j)
55 dp[t][j] += dp[u][j-1] - dp[t][j-2];
56 dp[t][1] += dp[u][0];
57 calc(t);
58 }
59 }
60
61 int main()
62 {
63 read(n),read(k);
64 for(int i = 1;i i)
65 {
66 read(f),read(t);
67 insert(f,t);insert(t,f);
68 }
69 for(int i = 1;i <= n;++ i)
70 read(val[i]);
71 dfs(1);
72 memset(vis,0,sizeof(vis));
73 calc(1);
74
75 for(int i = 1;i <= n;++ i)
76 printf("%d\n",dp[i][k]);
77 return 0;
78 }
京公网安备 11010802041100号