洛谷 P3047 [USACO12FEB]附近的牛Nearby Cows

P3047 [USACO12FEB]附近的牛Nearby Cows

dfs+前缀和处理
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #define N 1000010
 5 using namespace std;
 6 int val[N],front[N],nextt[N],to[N],fa[N];
 7 int n,m,r,c,x,y,k,tot;
 8 int hkd[100001][21];
 9 inline void add(int u,int v)
10 {
11     to[++tot]=v;nextt[tot]=front[u];front[u]=tot;
12     to[++tot]=u;nextt[tot]=front[v];front[v]=tot;
13 }
14 void dfs(int now,int from)
15 {
16     fa[now]=from;hkd[now][0]=val[now];
17     for(int i=front[now];i;i=nextt[i])
18     {
19         if(to[i]==from) continue;
20         dfs(to[i],now);
21         for(int j=1;j<=k;j++)
22             hkd[now][j]+=hkd[to[i]][j-1];
23     }
24 }
25 
26 void cal(int now)
27 {
28     int K=k,ans=0;ans=hkd[now][k];
29     while(now!=1 && K)
30     {
31         K--;ans+=hkd[fa[now]][K];
32         if(K) ans-=hkd[now][K-1];
33         now=fa[now];
34     }
35     printf("%d
",ans);
36 }
37 
38 int main()
39 {
40     scanf("%d%d",&n,&k);
41     for(int i=1;i<n;i++)
42     {
43         scanf("%d%d",&x,&y);
44         add(x,y);
45     }
46     for(int i=1;i<=n;i++) scanf("%d",&val[i]);
47     dfs(1,0);
48     for(int i=1;i<=n;i++)
49         for(int j=1;j<=k;j++)
50             hkd[i][j]+=hkd[i][j-1];
51     for(int i=1;i<=n;i++) cal(i);
52     return 0;
53 }
View Code