You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

72 lines
2.0 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N << 1;
const int K = 25;
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int f[N][K]; // f[i][j]:如果根是1号节点时i号节点最远走j步可以获取到的所有点权和
int g[N][K];
int val[N]; // 点权数组
int n, k;
void dfs1(int u, int fa) {
// 初始化当遍历到u节点时u的拆分状态中最起码包含了自己的点权值
for (int i = 0; i <= k; i++) f[u][i] = val[u];
// 枚举u的每一个子节点
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue; // 如果是u的父亲那么就跳过,保证只访问u的孩子
// 先递归,// 递归填充v节点的信息
dfs1(v, u);
// 再利用子节点信息更新父节点信息
for (int j = 1; j <= k; j++) f[u][j] += f[v][j - 1];
}
}
// 换根dp
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
g[v][0] = val[v]; // 走0步,只有自己一个点
g[v][1] = f[v][1] + val[u]; // 走1步,包含自己下面子树一层+父节点
// 如果走2步及以上最多k步以内
for (int j = 2; j <= k; j++) g[v][j] = f[v][j] + g[u][j - 1] - f[v][j - 2];
// 再递归,利用父更新子
dfs2(v, u);
}
}
int main() {
// 初始化链式前向星
memset(h, -1, sizeof h);
cin >> n >> k;
for (int i = 1; i < n; i++) { // n-1条边
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for (int i = 1; i <= n; i++) cin >> val[i]; // 点权
// 1、自底向上
dfs1(1, 0);
// 2、换根dp
for (int i = 0; i <= k; i++) g[1][i] = f[1][i];
dfs2(1, 0);
// 输出结果
for (int i = 1; i <= n; i++) cout << g[i][k] << endl;
return 0;
}