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

whyl

2019-10-30 09:19:17

Solution

发布一篇换根的题解 发现大家的做法基本上是容斥做的 填一篇换根的题解 换根的题目的大体思虑是先指定一个根 做出预处理 然后我们换根就只需要考虑父亲节点和儿子节点之间维护的信息 然后我们考虑一下贡献就可以了 定义状态为f[i][j]表示在i节点属于子树距离为j的节点 转移显然f[i][j]=sigma(f[son[x][j-1]]) cut表示抛去原来的贡献 link表示加上贡献 回溯时把根换回来就好了 ```cpp #include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1; char p=getchar(); while(!isdigit(p)){ if(p=='-') f=-1; p=getchar(); } while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar(); return x*f; } const int maxn=1e5+5; int n,k,dp[maxn][23],head[maxn],ver[maxn<<1],nxt[maxn<<1],cnt,ans[maxn]; inline void add(int x,int y){ nxt[++cnt]=head[x]; head[x]=cnt; ver[cnt]=y; } inline void dfs_pre(int x,int fa){ for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y==fa) continue; dfs_pre(y,x); for(int j=1;j<=k;j++) dp[x][j]+=dp[y][j-1]; } } inline void cut(int root1,int root2){ for(int i=1;i<=k;i++) dp[root1][i]-=dp[root2][i-1]; } inline void link(int root1,int root2){ for(int i=1;i<=k;i++) dp[root1][i]+=dp[root2][i-1]; } inline void change_root(int x,int y){ cut(x,y); link(y,x); } inline void dfs(int x,int fa){ for(int i=0;i<=k;i++) ans[x]+=dp[x][i]; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y==fa) continue; change_root(x,y); dfs(y,x); change_root(y,x); } } int main(){ n=read();k=read(); for(int i=1;i<n;i++){ int x=read(),y=read(); add(x,y);add(y,x); } for(int i=1;i<=n;i++) dp[i][0]=read(); dfs_pre(1,0); // for(int i=1;i<=n;i++){ // for(int j=0;j<=k;j++){ // cout<<dp[i][j]<<" "; // } // cout<<endl; // } // cout<<endl; dfs(1,0); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } ```