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[4][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[0] + i);
    assert(0 <= F[0][i] && F[0][i] <= 1000);
    F[1][i] += F[0][i];
    for(int j = 0; j < E[i].size(); j++) {
      F[1][E[i][j]] += F[0][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]);
}