1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
#define maxm 21
using namespace std;
int n, m, a[maxn];
struct Edge {
int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
int f[maxn][maxm], g[maxn][maxm];
void dfs(int u, int fa) {
f[u][0] = a[u];
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u);
for (int j = 1; j <= m; ++j)
f[u][j] += f[v][j - 1];
}
}
void Dfs(int u, int fa) {
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
g[v][0] = a[v];
for (int j = 1; j <= m; ++j)
g[v][j] = f[v][j] + g[u][j - 1] - (j > 1 ? f[v][j - 2] : 0);
Dfs(v, u);
}
}
int main() { memset(head, -1, sizeof head);
cin >> n >> m;
for (int i = 1; i < n; ++i) {
int x, y; scanf("%d%d", &x, &y);
add_edge(x, y); add_edge(y, x);
}
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
dfs(1, 0); for (int i = 0; i <= m; ++i) g[1][i] = f[1][i]; Dfs(1, 0);
for (int i = 1; i <= n; ++i) {
int res = 0;
for (int j = 0; j <= m; ++j) res += g[i][j];
printf("%d\n", res);
}
return 0;
}
|