感觉这类问题很少？算了，还是拿出来水一下吧qwq...
首先来看一道例题：POJ3585
一句话题意：树上任意源点多汇点最大流
你看这不就是个最大流的板子题吗？我先建个图，然后跑最大流，然后，，，然后？
然后
All the elements are nonnegative integers no more than 200000.
还多测... mdzz
好了来讲换根吧。
首先有一个暴力(dp)，我们先考虑以(rt=1)的情况((1)为根)，令(dp[x])表示(rt)为根时，直接往节点(x)灌水，然后向(x)的子树内流的最大流量
有如下转移
特别的，如果(v)在(1)为根的情况下是叶节点的话，(dp[x] += w(x,v))（(w(x,y))表示边((x,y))的容量）
然后(O(n))枚举(rt)，再(O(n))dp，就可以收获一个(n^2)的优秀做法。
发现换根过后树的变化实际上没有那么大，我们令(f[x])表示(rt=x)时的(dp[x])。
考虑把(rt)换到(x)的一个儿子(v)上，由于(x)为根的时候(v)也是(x)的一个儿子，所以(v)会对(f[x])产生(min(dp[v],w(x,v)))的贡献
那么(f[x]-min(dp[v],w(x,v)))就得到了除了子树(v)以外的部分，它在换根后会成为(v)的一棵子树
所以(f[v] = dp[v]+minleft(w_{x,v},f[x]-min(dp[v],w_{x,v}) ight))（嘛...括号太多看不清楚...所以这里就直接(w_{x,v})了qwq）
需要特判(x)只有(v)一个儿子的时候(f[v] = dp[v]+w_{x,v})（就直接从(v)流向(x)了）
所以Code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;
#define fore(i,x) for(int i=head[x],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)
const int N=3e5+10;
struct edge
{
int to,nxt,w;
}e[N<<1];
int head[N],cnt;
inline void ade(int x,int y,int w)
{e[++cnt]=(edge){y,head[x],w},head[x]=cnt;}
inline void addedge(int x,int y,int w)
{ade(x,y,w),ade(y,x,w);}
int n,sum[N],f[N],deg[N]; // 这里的sum就是上面的dp辣
void dfs(int x,int prev)
{
fore(i,x) if(v!=prev)
{
dfs(v,x);
if(deg[v]==1) sum[x]+=w;
else sum[x]+=min(sum[v],w);
}
}
void getans(int x,int prev)
{
fore(i,x) if(v!=prev)
{
if(deg[x]==1) f[v]=sum[v]+w;
else f[v]=sum[v]+min(f[x]-min(sum[v],w),w);
getans(v,x);
}
}
void sol()
{
memset(deg,0,sizeof(deg));
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
cnt=0;
scanf("%d",&n);
for(int x,y,w,i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
++deg[x],++deg[y];
}
dfs(1,0);
f[1]=sum[1],getans(1,0);
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
printf("%d
",ans);
}
int main()
{
int T; scanf("%d",&T); while(T--)sol();
return 0;
}
于是再来看一道题：LuoguP3478
同样换根，令(f[x])表示(x)为根时的所有节点的深度和。
考虑将根换到(x)的一个儿子(v)上，那么对于子树(v)里面的节点，他们的深度会减少(1)，其他节点深度会加上(1)，即（(size_v)表示(v)以(1)为根时的子树大小）
先以(1)为根求出(size)，然后换根就好了
十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fore(i,x) for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
const int N=1e6+10;
int n;
struct edge
{
int to,nxt;
}e[N<<1];
int head[N],cnt=0;
inline void ade(int x,int y)
{e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline void addedge(int x,int y)
{ade(x,y),ade(y,x);}
ll f[N],dep[N];
int siz[N];
void dfs(int x,int prev,int deep)
{
dep[x]=deep,siz[x]=1;
fore(i,x) if(v!=prev)
dfs(v,x,deep+1),siz[x]+=siz[v];
}
void getans(int x,int prev)
{
fore(i,x) if(v!=prev)
{
f[v]=f[x]+n-2ll*siz[v];
getans(v,x);
}
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),addedge(x,y);
dfs(1,0,0);
for(int i=1;i<=n;i++) f[1]+=dep[i];
getans(1,0);
ll mx=0; int ans=0;
for(int i=1;i<=n;i++)
if(f[i]>mx) mx=f[i],ans=i;
printf("%d
",ans);
return 0;
}