换根dp
闲话：换根dp其实常见的还是挺简单的 ，就是太菜了，之前学了两次都忘了，写篇总结留给下次忘了再看。
多锻炼身体，身体zui重要。
换根dp一般分为三个步骤
1、先指定一个根节点
2、一次dfs统计子树内的节点对当前节点的贡献
3、一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案
-
P3478 [POI2008]STA-Station—入门题
本题是入门题，问的简单明了，哪个节点为根节点可以使深度之和最大。
思路：
1、先任意以一个节点为根节点跑一遍dfs1，记录需要的信息，本题需要去记录每个节点以节点1为根节点在树中包含自身的子树的节点数和在树中的深度
2、然后再去跑一遍dfs2，去记录分别以某个节点为根节点的值
3、遍历答案数组ans，找出深度之和最大的节点
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int to[N*2],nex[N*2],fir[N],idx;
int n,maxn,id;
int dep[N],sz[N],ans[N];
void add(int u,int v){
to[++idx]=v;
nex[idx]=fir[u];
fir[u]=idx;
}
void dfs1(int u,int fa){
sz[u]=1,dep[u]=dep[fa]+1;
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
dfs1(v,u);
sz[u]+=sz[v];
}
}
}
void dfs2(int u,int fa){
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
ans[v]=ans[u]+n-2*sz[v];
dfs2(v,u);
}
}
}
signed main(){
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,0);
// for(int i=1;i<=n;i++) ans[1]+=dep[i];
// for(int i=1;i<=n;i++) cout<<sz[i]<<" "; //输出以节点1为根节点，每个节点包含自身的子树中节点个数
// puts("");
// for(int i=1;i<=n;i++) cout<<dep[i]<<" "; //输出以节点1为根节点，每个节点在树中的深度，节点1深度为1
// puts("");
dfs2(1,0);
for(int i=1;i<=n;i++){
if(ans[i]>maxn){
maxn=ans[i];
id=i;
}
}
cout<<id<<endl;
}
-
P2986 [USACO10MAR]Great Cow Gathering G–入门题+
读完题就应该知道这也是一个树形结构，再想一下会发现这应该也是换根dp的题目。废话，本文肯定都是换根dp题
发现：
这一题不像上一个题一样，上一个题可以理解为边值都是1的树，是一个只有点权的树。而这个题是一颗又有边权又有点权的树~~（不知道叫什么，乱命名）~~
思路：
1、先任意以一个节点为根节点跑一遍dfs1，记录需要的信息，本题需要去记录每个节点以节点1为根节点，子树中每个节点都根节点1的距离，以及每个节点的子树中的奶牛数量
2、因为是以节点1为根节点跑的dfs1，所有开始认为所有奶牛到节点1集合，先初始求出到节点1集合的不方便值。
3、然后再去跑一遍dfs2，去记录分别以其他某个节点为根节点的值。（本题这一步有点前缀和的思想）
4、遍历答案数组dp，找出最小的不方便值的节点
//https://www.luogu.com.cn/problem/P2986
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int inf=1e15;
int n,a[N],sum;
int to[N*2],nex[N*2],val[N*2],fir[N],idx;
//数组sz[i]表示以i为根节点的子树中奶牛的数量 ，这里根节点是1开始 有点前缀和的思想
//数组dis[i]表示节点i到节点1的距离，数组dp[i]表示会议地点选择节点i时的代价
int dis[N],sz[N],dp[N],minn=inf;
void add(int u,int v,int w){
to[++idx]=v;
val[idx]=w;
nex[idx]=fir[u];
fir[u]=idx;
}
void dfs1(int u,int fa){
sz[u]=a[u];
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
dis[v]+=dis[u]+val[i];
dfs1(v,u);
sz[u]+=sz[v];
}
}
}
void dfs2(int u,int fa){
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
dp[v]=dp[u]-sz[v]*val[i]+(sz[1]-sz[v])*val[i];
dfs2(v,u);
}
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
dfs1(1,0);
for(int i=2;i<=n;i++) dp[1]+=dis[i]*a[i];
dfs2(1,0);
for(int i=1;i<=n;i++) minn=min(minn,dp[i]);
cout<<minn<<endl;
}
-
CF1187E Tree Painting–经典题
大家别看这个题目对应的cf分有点高就不敢写，估计是刚出来的时候分高，学了之后应该感觉类似入门题思路：好好学习上面做题解题技巧和思想，就可以想办法去切了这题了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n;
int to[N*2],nex[N*2],fir[N*2],idx;
int sz[N],dp[N],f[N],maxn;
void add(int u,int v){
to[++idx]=v;
nex[idx]=fir[u];
fir[u]=idx;
}
void dfs1(int u,int fa){
sz[u]=1;
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
dfs1(v,u);
sz[u]+=sz[v];
dp[u]+=dp[v];
}
}
dp[u]+=sz[u];
}
void dfs2(int u,int fa){
for(int i=fir[u];i;i=nex[i]){
int v=to[i];
if(v!=fa){
f[v]=n+f[u]-2*sz[v];
dfs2(v,u);
}
}
}
signed main(){
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,0);
f[1]=dp[1];
dfs2(1,0);
for(int i=1;i<=n;i++) maxn=max(maxn,f[i]);
cout<<maxn<<"\n";
}
总结
换根dp其实就是跑两遍dfs，注意一下转移方程，剩下的就好写了。还是存在一定套路的，多写几题练练手就会有所体会
题目：
1、CF708C Centroids
2、P6419 [COCI2014-2015#1] Kamp
都挺经典的，可以写写，之后有时间再来更新题目