本文主要是介绍[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 ;
}这篇关于[ACM学习] 树形dp之换根的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
