NC201400 树学题解

树学

https://ac.nowcoder.com/acm/problem/201400

一.题解

这道题又是一道换根dp板子题，代码结构与 Accumulation Degree 这道题基本一致，唯一不同的就是转移了【不过转移的时候，因为方程的原因不需要特殊考虑叶节点】

我们先套路的设 $dp[i]$ 表示以 $i$ 为根的子树中，所有点的深度和，现在，我们来想想转移。

我们发现，如果我们要从 $i$ 的一个儿子v转移到i的话，以v为根的子树中的所有节点的深度都加了1，现在我们就不能够直接求值了，怎么办呢？很简单，我们发现，既然以v为根的子树中的所有节点的深度都加了1，那么，一共增加的值，不就正好是以v为根的子树中节点的个数嘛？

所以，我们只需要再维护一个以i为根的子树的大小 $siz[i]$ 即可

那么，我们就可以很简单的推出转移:

$dp[i]=$ $\sum_{v\in son(i)}(dp[v]+siz[v])$

$siz[i]=$ $1(i本身)+\sum_{v\in son(i)}siz[v]$

这样，我们一遍dfs就可以求出所有 $dp[i]$ 了！

现在，我们考虑换根dp

我们假设将根 $x$ 换成了它的一个儿子 $y$ ，那么，同样的，改变的只是 $x$ 和 $y$ 的子树，我们将这个"影响"修改一下即可~

首先， $dp[i]-=(dp[v]+siz[v])$ (减去v的贡献)

然后， $siz[i]-=siz[v],siz[v]+=siz[i]$ (修改两个点的子树大小)

最后， $dp[v]+=(dp[i]+siz[i])$ (加上i的贡献)

为什么是这个顺序呢？因为修改 $dp[i]$ 的时候， $dp[v]$ 和 $siz[v]$ 必须和以前一样（因为我们是从这两个值转移过来的），然后要修改 $dp[v]$ 的话， $dp[i]$ 和 $siz[i]$ 又必须是修改后，没加v的贡献的值，所以，这样安排修改顺序是很好的。（当然，你非要用其他顺序的话，我也无话可说，只是要注意修改的方法有可能会不同）

最后，我们每次统计下以任意点为根时， $dp[i]$ 的值的最小值即可~

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
struct node{
    int v,nex;
}t[N<<1];
int dp[N],siz[N];
int las[N],len,ans=1e17;
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs1(int now,int fa){
    siz[now]=1;
    for(int i=las[now];i;i=t[i].nex){
        int v=t[i].v;
        if(v!=fa){
            dfs1(v,now);
            siz[now]+=siz[v];
            dp[now]+=(dp[v]+siz[v]);
        }
    }
}
inline void dfs2(int now,int fa){
    ans=min(ans,dp[now]);
    for(int i=las[now];i;i=t[i].nex){
        int v=t[i].v;
        if(v!=fa){
            int pas1=siz[now],pas2=siz[v];
            int Pas1=dp[now],Pas2=dp[v];//继续偷懒
            dp[now]-=(dp[v]+siz[v]);
            siz[now]-=siz[v];siz[v]+=siz[now];
            dp[v]+=(dp[now]+siz[now]);
            dfs2(v,now);
            siz[now]=pas1,siz[v]=pas2;
            dp[now]=Pas1,dp[v]=Pas2;
        }
    }
}
signed main(){
    int n;
    scanf("%lld",&n);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,1);dfs2(1,1);
    printf("%lld",ans);
    return 0;
}