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

2019-10-30 09:19:17


发布一篇换根的题解

发现大家的做法基本上是容斥做的

填一篇换根的题解

换根的题目的大体思虑是先指定一个根

做出预处理

然后我们换根就只需要考虑父亲节点和儿子节点之间维护的信息

然后我们考虑一下贡献就可以了

定义状态为f[i][j]表示在i节点属于子树距离为j的节点

转移显然f[i][j]=sigma(f[son[x][j-1]])

cut表示抛去原来的贡献

link表示加上贡献

回溯时把根换回来就好了

#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;
}