题解P3047 [USACO12FEB]附近的牛Nearby Cows

题目：P3047 [USACO12FEB]附近的牛Nearby Cows

本题的意思就是求离每个点距离不超过k的点的权值和。

然后我们很容易想到，f[x][j]=Σf[v][j-1](v∈son[x])

然后我们会发现有重复的，于是容斥原理运用一下。

因为每次v扩展一步到x，到x距离为j-2的点肯定有一部分是到v距离为j-1的点，就会被重复计算。

大概这样，然后每次f[x][j]-=f[v][j-2]*(size[v]-1)。

为啥-1呢，因为你还要保留原来那一份。

但是记录这题的原因是，我发现树形dp可以不写dfs！

本来是写了dfs，感觉没法调，然后就看了题解，才知道树形dp也可以不在dfs里面进行！

因为我们这次不需要每次更新扩大size[x]，我们只关心和他相连的点怎么转移过来没所以我们不用dfs进行dp。

一个小细节就是数组多开点防止越界。

 1 #include<cstdio>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 int h[N],nxt[N],adj[N],s[N],u,v,t,n,k; 
 6 long long f[N/5][21];
 7 il void add(){
 8     nxt[++t]=h[u],h[u]=t,adj[t]=v,++s[u];
 9     nxt[++t]=h[v],h[v]=t,adj[t]=u,++s[v];
10 }
11 il void fr(int &num){
12     num=0;char c=getchar();int p=1;
13     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
15     num*=p;
16 }
17 il void lfr(long long &num){
18     num=0;char c=getchar();int p=1;
19     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
20     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
21     num*=p;
22 }
23 int main(){ 
24     fr(n),fr(k);
25     for(it i=1;i<n;++i) fr(u),fr(v),add();
26     for(it i=1;i<=n;++i) lfr(f[i][0]);
27     for(it j=1;j<=k;++j)
28         for(u=1;u<=n;++u){
29             for(it i=h[u];i;i=nxt[i])
30                 f[u][j]+=f[adj[i]][j-1];
31             j>1?f[u][j]-=1ll*(s[u]-1)*f[u][j-2]:f[u][1]+=f[u][0];
32         }
33     for(it i=1;i<=n;++i)
34         printf("%lld
",f[i][k]);
35     return 0;
36 }

View Code

题解P3047 [USACO12FEB]附近的牛Nearby Cows

相关推荐