医院设置（换根DP）

• 分析

换根DP
顾名思义，就是换根做的DP，一开始用父节点作为根节点求一边DP，第二次就用
子节点为根节点做一遍DP，此时子节点的信息就可以由父节点来更新
dp[i]:在节点i建立医院，其他节点到该点的距离和
w[i]:表示节点i中居民的人数
cnt[i]:表示dfs时以节点i为根节点向下走的所有节点的人数之和
sum表示所有节点的人数总和，如果我们dfs时从节点u开始搜索，则cnt[u]==sum

dfs1:由子节点j更新父节点u（u会有多个子节点）
以j为根节点的子树到u的距离与到j的距离只差1，所以更新需要额外加上cnt[j]
dp[u]+=dp[j]+cnt[j];

dfs2:由父节点fa更新子节点u
举个例子，以题目中给出的图来看：
dp[1]=1*w[2]+0*w[1]+1*w[3]+2*w[4]+2*w[5]
dp[2]=0*w[2]+1*w[1]+2*w[3]+3*w[4]+3*w[5]
     =dp[1]-w[2]+(w[1]+w[3]+w[4]+w[5])
     =dp[1]-cnt[2]+(sum-cnt[2])
由以上两个式子可以发现,用父节点fa更新子节点u时,递推式如下：
dp[u]=dp[fa]+(sum-cnt[u])-cnt[u]

• C++代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=110,M=N*2;
int h[N],e[M],ne[M],w[N],idx;
int cnt[N],dp[N];
int n,sum;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int fa){//父节点为根，子节点更新父节点
    cnt[u]=w[u],dp[u]=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs1(j,u);
        cnt[u]+=cnt[j];
        dp[u]+=dp[j]+1*cnt[j];
    }
}
void dfs2(int u,int fa){//子节点为根时，父节点更新子节点
    if(fa!=-1){
        dp[u]=dp[fa]+(sum-cnt[u])-cnt[u];
    }
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs2(j,u);
    }
}
int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>w[i]>>a>>b;
        sum+=w[i];
        if(a)add(i,a);
        if(b)add(i,b);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    int ans=1e9;
    for(int i=1;i<=n;i++)
        if(dp[i]<ans)
            ans=dp[i];
    cout<<ans<<endl;
    return 0;
}