二次扫描与换根
说实话，我很少为树型(DP)写文章，一来这是我最喜欢的一类(DP)了，二来是……（不知道要编啥了(QAQ)
不过这种方法极其有趣，让我有一种想写的欲望。
废话不多说，开题：
总结一下题意：无根树，流量，最大。
好吧讲真的我第一反应是最大流呵呵呵呵……
但是这个(N)极其不友好啊（(200000)你是要干啥？）
显然最大流是弄不了了，看一下我们似乎只用上了流量和最大这两个条件无根树还没用上呢。
用树型(DP)的方法显然是可以的，但是如果我们暴力跑的话显然会(TLE)。
暴力做法：每次以一个节点为根，跑一边树型(DP)，最后取(Max)。
再分析一下我们我们的暴力，发现我们并没有用到每一次(DP)的结果，相当于是浪费了时间。
那么我们能不能将前面的计算结果理由上呢？显然是可以的。
接下来就是我们的二次扫描与换根。
如图：我们定义一个(d[x])，用于记录当我们选(Root)为全树的根时，以(x)为根的子树的流量(Max)。
（我个人习惯将(Root)定义为(1)，你们自己看着办。）
那么，我们就可以利用到先前跑出的答案了。
即有：(f[y]=d[y]+min(f[x]-min(d[y],dis(x,y)),dis(x,y));)
(deg)为(1)时特判一下即可，上代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=200010;
int d[N],deg[N],f[N];
int n,num_edge,head[N];
struct Edge{int next,to,dis;} edge[N*2];//双向边，开两倍一定不能忘了！
inline void add(int from,int to,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].dis=dis;
edge[num_edge].to=to;
head[from]=num_edge;
}
inline void Work(int pos,int fa)
{
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=fa)
{
Work(edge[i].to,pos);
if(deg[edge[i].to]==1) d[pos]+=edge[i].dis;
else d[pos]+=min(d[edge[i].to],edge[i].dis);
}
}
inline void Dfs(int pos,int fa)
{
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=fa)
{
if(deg[pos]==1) f[edge[i].to]=d[edge[i].to]+edge[i].dis;
else f[edge[i].to]=d[edge[i].to]+min(f[pos]-min(d[edge[i].to],edge[i].dis),edge[i].dis);
Dfs(edge[i].to,pos);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Text1.in","r",stdin);
#endif
int T=read();
while(T--)
{
memset(f,0,sizeof(f));
memset(d,0,sizeof(d));
memset(deg,0,sizeof(deg));
memset(head,0,sizeof(head));
n=read();num_edge=0;
for(int i=1,u,v,d;i<n;i++)
{
u=read(),v=read(),d=read();
add(u,v,d),add(v,u,d);
deg[u]++,deg[v]++;
}
int ans=0;
Work(1,0);f[1]=d[1];Dfs(1,0);
for(int i=1;i<=n;i++) ans=max(f[i],ans);
printf("%d
",ans);
}
}
有关换根，我再来补一些锅，相当于是我们要求对全图以每个子节点为根(DP)一遍时，就可以考虑换根。
换根时，因为按照我们钦定的(Root)，一个节点的父亲一定是算出了以他为根的答案。
那么我们在(DP)时就只要处理一下每个点去掉某个儿子后的答案即可快速换根。