P3047 [USACO12FEB]附近的牛Nearby Cows

 5 #define re register  6 using namespace std;  7  8 template <typename T> void in(T &x) {  9 x = 0; T f = 1; char ch = getchar(); 10 while(!isdigit(ch)) {if(ch == ‘-‘) f = -1; ch = getchar();} 11 while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();} 12 x *= f; 13 } 14 15 template <typename T> void out(T x) { 16 if(x < 0) x = -x,putchar(‘-‘); 17 if(x > 9) out(x/10); 18 putchar(x%10 + 48); 19 } 20 21 int n,k; 22 const int N = 100007; 23 struct edge { 24 int v,nxt; 25 }e[N<<1]; int tot,head[N]; 26 void add(int u,int v) {e[++tot] = (edge){v,head[u]}; head[u] = tot;} 27 28 int f[2][N][25],c[N]; 29 30 void dfs1(int u,int fa) { 31 up(i,0,k) 32 f[0][u][i] = c[u];
33 for(re int i = head[u]; i ; i = e[i].nxt) { 34 int v = e[i].v; 35 if(v == fa) continue; 36  dfs1(v,u); 37 up(i,1,k) 38 f[0][u][i] += f[0][v][i-1]; 39  } 40 } 41 42 void dfs2(int u,int fa) { 43 44 f[1][u][0] = c[u]; 45 up(i,1,k) f[1][u][i] = f[1][fa][i-1] - f[0][u][i-2] + f[0][u][i]; 46 //别忘了+f[0][u][i]  47 for(re int i = head[u]; i ; i = e[i].nxt) { 48 int v = e[i].v; 49 if(v == fa) continue; 50  dfs2(v,u); 51  } 52 } 53 54 int main() { 55 freopen("input.txt","r",stdin); 56 in(n); in(k); 57 int u,v; 58 up(i,n-1) { 59 in(u); in(v); 60  add(u,v); add(v,u); 61  } 62 up(i,n) in(c[i]); 63 dfs1(1,0); 64 65 up(i,k) 66 f[1][0][i] = f[0][1][i-1]; 67 //必须给0号节点赋初值  68 dfs2(1,0); 69 70 up(i,n) out(f[1][i][k]),putchar(‘n‘); 71 return 0; 72 }