[ACM学习] 树形dp之换根

算法概述

总的来说：

题目描述：一棵树求哪一个节点为根时，XXX最大或最小

分为两步：1. 树形dp? 2. 第二次dfs

问题引入

如果暴力就是 O(n^2) ，

当从1到2的时候，2及其子树所有的深度都减一，其它的点，所有的深度都加一。写成递推方程如下：

代码

思路是：第一遍 dfs 遍历的时候先把以某一确定点为根的其它各点深度和算出来，再来看我们的状态转移方程，还需要各个点的大小值，所以在遍历的时候就把它给维护好。

siz数组刚开始全为1

第二遍的时候，就是在用公式啦。

在main 函数

难点在于不同点之间怎么转移

复杂度O(n)

例题

按换根dp的思路，进行状态转移时

从1到2，原来到1的路径和ans[1] ，到2的路径和 ans[2] ，变化就是 ：以2为子树的结点，路径长度少了1到2的长度，其它结点，路径长度多了1到2的长度

sum[i] : 以 i 为子树的权值和

所以，方程上的变化就是：ans[2] = ans[1] - sum[2]*（1与2之间的路径长）+ （sum[1]-sum[2]）*（1与2之间的路径长）

代码

void dfs(int x,int fa){
    siz[x]=1;sum[x]=c[x];
    for(int i=head[x];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==fa)continue;
        dist[v]=dist[x]+edge[i].dis;
        dfs(v,x);
        siz[x]+=siz[v];
        sum[x]+=sum[v];
    }
    return ;
}
void dfs1(int x,int fa){
    for(int i=head[x];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==fa)continue;
        f[v]=f[x]-sum[v]*edge[i].dis+(tot-sum[v])*edge[i].dis;
    }
    return ;
}

dfs(1,0);
    for(int i=1;i<=n;i++){
        f[1]+=dist[i]*c[i];  //是把所有的点记录好到1的距离后，再全部来乘权值。
    }
    dfs1(1,0);
    ll ans=101010101000;
    for(int i=1;i<=n;i++){
        ans=min(ans,f[i]);
    }
    cout<<ans<<endl;

struct Edge{
    int nex,to,dis;
}edge[maxn<<1];
int siz[maxn],head[maxn],cnt,tot;
void add(int from,int to,int dis){
    edge[++cnt]={head[from],to,dis};
    head[from]=cnt;
    return ;
}