题解 P3047 【[USACO12FEB]附近的牛Nearby Cows】
whyl
2019-10-30 09:19:17
发布一篇换根的题解
发现大家的做法基本上是容斥做的
填一篇换根的题解
换根的题目的大体思虑是先指定一个根
做出预处理
然后我们换根就只需要考虑父亲节点和儿子节点之间维护的信息
然后我们考虑一下贡献就可以了
定义状态为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;
}
```