P3047 [USACO12FEB] Nearby Cows G-526互联

#include <iostream>
#include <vector>
using namespace std;
const int N = 100010,M = 30;
int n,m;
int w[N];
vector <int> g[N];
int f[N][M],ans[N][M];
void DP1 (int u,int fa) {
	for (int i = 0;i <= m;i++) f[u][i] = w[u];
	for (int x : g[u]) {
		if (x == fa) continue;
		DP1 (x,u);
		for (int i = 1;i <= m;i++) f[u][i] += f[x][i - 1];
	}
}
void DP2 (int u,int fa) {
	for (int x : g[u]) {
		if (x == fa) continue;
		ans[x][1] += w[u];
		for (int i = 2;i <= m;i++) ans[x][i] += ans[u][i - 1] - f[x][i - 2];  //利用上一层节点的答案减去重复的子树x
		DP2 (x,u);
	}
}
int main () {
	cin >> n >> m;
	for (int i = 1;i <= n - 1;i++) {
		int a,b;
		cin >> a >> b;
		g[a].push_back (b),g[b].push_back (a);
	}
	for (int i = 1;i <= n;i++) cin >> w[i];
	DP1 (1,-1);
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= m;j++) ans[i][j] = f[i][j];
	}
	DP2 (1,-1);
	for (int i = 1;i <= n;i++) cout << ans[i][m] << endl;
	return 0;
}