Solution Notes: This problem can be solved fairly easily by dynamic programming in O(NK) time. Let A(x,r) denote the number of cows within a radius of r of node x. As a base case, A(x,0) = C(x). We then compute A(x,1) for all nodes x, then A(x,2) for all nodes x, up to A(x,k) for all nodes x. To compute A(x,r), we sum up A(y,r-1) over all neighbors y of x, and then subtract out A(x,r-2) times the degree of x (the number of neighbors of x) to correct for double-counting. The total running time for each fixed value of r is just O(N), since the sum of the degrees of all the nodes in a graph is twice the number of edges, which for a tree is O(N).

``````
#include <iostream>
#include <vector>
#include <cstdio>
#include <cassert>

using namespace std;

#define MAXN 100000
vector<int> E[MAXN];
int F[MAXN];

int main() {
freopen("nearcows.in", "r", stdin);
freopen("nearcows.out", "w", stdout);
int N, K; scanf("%d%d", &N, &K);
assert(1 <= N && N <= 100000 && 1 <= K && K <= 20);
for(int i = 1; i < N; i++) {
int u, v; scanf("%d%d", &u, &v); u--; v--;
assert(0 <= u && u < N && 0 <= v && v < N);
E[u].push_back(v);
E[v].push_back(u);
}
for(int i = 0; i < N; i++) {
scanf("%d", F + i);
assert(0 <= F[i] && F[i] <= 1000);
F[i] += F[i];
for(int j = 0; j < E[i].size(); j++) {
F[E[i][j]] += F[i];
}
}
for(int i = 2; i <= K; i++) {
for(int j = 0; j < N; j++) {
F[i & 3][j] = -(E[j].size() - 1) * F[i - 2 & 3][j];
for(int k = 0; k < E[j].size(); k++) {
F[i & 3][j] += F[i - 1 & 3][E[j][k]];
}
}
}
for(int i = 0; i < N; i++) printf("%d\n", F[K & 3][i]);
}
``````