Accumulation Degree
大致题意：有一棵流量树，它的每一条边都有一个正流量，树上所有度数为一的节点都是出口，相应的树上每一个节点都有一个权值，它表示从这个节点向其他出口可以输送的最大总流量。我们的任务就是求这个最大总流量。
$ solution: $
这一道题需要仔细思考其性质，我们发现如果我们把某一个节点当做是这棵树的根，并求出了这一个点的权值，那么与它相连的节点我们也可以求出来。这是二次扫描和换根法的前提条件。现在我们详细的分析一下这一题的性质：如果我们现在有两个节点 $ i $ 和 $ j $ ， $ j $ 是 $ i $ 的儿子， $ i $ 是根节点，然后我们用树形 $ DP $ 求出了 $ i $ 号结点的权值（这个过程里我们肯定会求得 $ j $ 流向 $ j $ 这可子树的流量），这样我们发现 $ j $ 的权值是可以通过 $ i $ $ O(1) $ 求出来的。因为我们已经求出了 $ j $ 流向 $ j $ 这棵子树的流量，然后只要我们求出 $ j $ 通过 $ i $ 流向其他子树的流量就可以得出 $ j $ 的权值，而这个就是用 $ i $ 的权值减去它流向 $ j $ 的流量，然后再和 $ e( i,j ) $ 这条边的流量取最小值即可。然后我们发现我们的 $ j $ 节点已经拥有了作为一个根节点的条件，所以 $ j $ 又可以当做一个新的根节点来更新其他的节点。
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
const ll inf=(ll)1e12;
ll ans;
int t,n,id,top;
ll a[200005];
ll f[200005];
int du[200005];
int tou[200005];
bool vis[200005];
struct su{
int to,v,next;
}b[400005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar())) if(ch=='-')sign=1;
while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();
return sign?-res:res;
}
inline ll min(ll x,int y){
if(x<y)return x;
return y;
}
inline void add(int x,int y,int v){
b[++top].to=y; b[top].v=v;
b[top].next=tou[x]; tou[x]=top;
}
inline void dfs(int i){ vis[i]=1;
if(du[i]<2){a[i]=inf;return;}
for(rg j=tou[i];j;j=b[j].next){
rg to=b[j].to; if(vis[to])continue;
dfs(to); a[i]+=min(a[to],b[j].v);
}
}
inline void upd(int i,int fa,int v){
//cout<<i<<" "<<a[i]<<endl;
a[i]+=min(a[fa]-v,v); ans=max(ans,a[i]);
for(rg j=tou[i];j;j=b[j].next){
rg to=b[j].to;
if(to==fa||du[to]<2)continue;
upd(to,i,b[j].v);
}
}
int main(){
//freopen("in.in","r",stdin);
//freopen(".out","w",stdout);
t=qr();
while(t--){
n=qr(); top=0; ans=0; id=0;
if(n<2){puts("0");continue;}
if(n<3){qr();qr();cout<<qr()<<endl;continue;}
for(rg i=1;i<=n;++i)
a[i]=f[i]=du[i]=tou[i]=vis[i]=0;
for(rg i=1;i<n;++i){
rg x=qr(),y=qr(),v=qr();
add(x,y,v); add(y,x,v);
++du[x]; ++du[y];
if(du[x]>du[id])id=x;
if(du[y]>du[id])id=y;
//cout<<x<<" "<<du[x]<<" "<<y<<" "<<du[y]<<" "<<id<<" "<<du[id]<<endl;
}dfs(id); ans=a[id];
//cout<<id<<endl;
//cout<<"root:"<<id<<endl;
for(rg i=tou[id];i;i=b[i].next)
if(du[b[i].to]>1)upd(b[i].to,id,b[i].v);
printf("%lld
",ans);
}
return 0;
}