[ACM学习] 树形dp之换根-Toy模板网

这篇具有很好参考价值的文章主要介绍了[ACM学习] 树形dp之换根。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法概述

[ACM学习] 树形dp之换根,学习

总的来说：

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

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

问题引入

[ACM学习] 树形dp之换根,学习

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

[ACM学习] 树形dp之换根,学习

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

[ACM学习] 树形dp之换根,学习

代码

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

[ACM学习] 树形dp之换根,学习

siz数组刚开始全为1

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

[ACM学习] 树形dp之换根,学习

在main 函数

[ACM学习] 树形dp之换根,学习

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

[ACM学习] 树形dp之换根,学习

复杂度O(n)

例题

[ACM学习] 树形dp之换根,学习

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

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

[ACM学习] 树形dp之换根,学习

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

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

[ACM学习] 树形dp之换根,学习文章来源地址https://www.toymoban.com/news/detail-821919.html

代码

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

到了这里，关于[ACM学习] 树形dp之换根的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！