题意:有一个有n个节点，n-1条河道的树形水系，每个河道有一个最大容水量c[x][y]，源点(树的根节点)可以源源不断出水，树的叶子结点可以无限接纳水，而一个节点水的流量等于流过其儿子节点的水的流量之和，儿子节点水的流量不能超过其与父亲连边的最大容水量，求以哪个点为根(源点)时水流量最大，输出这个最大值即可.(n≤2×10^5)
首先最朴素的思路是枚举根节点然后跑树形DP,时间复杂度(O(N^2)),只能考虑从根节点下手优化时间复杂度.
第一次扫描,先任选一个点为根root,跑一次树形DP,预处理出每一个节点的最大流量(size[i]),设y是x的儿子节点,(w[i]=c[x][y])
如果y的度数为1,(size[x]+=w[i])
否则,(size[x]+=min(size[y],w[i]))
第二次扫描,从刚才选定为根的那个节点root出发DFS,DFS的过程中每递归到一个节点,就把该节点作为根节点计算流量,相当于是"换根".设(f[x])表示以x为源点的最大流量.
显然,(f[root]=size[root])
假设(f[x])已经求出,对于x的一个子节点y
如果x的度数为1,(f[y]=size[y]+w[i])
否则,(f[y]=size[y]+min(f[x]-min(size[y],w[i]),w[i]))
这里可能有点难理解.其实就是因为这是一棵"无根树",现在x是y的父节点,那么也有可能y是x的父节点,我在第一次扫描中求出了x是y的父节点时的(size[y]),现在我只要求把y当做x的父节点时的流量,然后相加就是(f[y])了.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int N=200005;
int ans,in[N],visit[N],size[N],f[N];
int tot,head[N],nxt[N*2],to[N*2],w[N*2];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
//树形DP预处理出size数组
inline void dfs1(int x){
visit[x]=1;size[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(visit[y])continue;
dfs1(y);
if(in[y]==1)size[x]+=w[i];
else size[x]+=min(size[y],w[i]);
}
}
//DFS计算"换根"后的解
inline void dfs2(int x){
visit[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(visit[y])continue;
if(in[x]==1)f[y]=size[y]+w[i];
else f[y]=size[y]+min(f[x]-min(size[y],w[i]),w[i]);
dfs2(y);
}
}
int main(){
int T=read();
while(T--){
tot=0;int n=read();
for(int i=1;i<=n;i++){
head[i]=0;in[i]=0;
visit[i]=0;size[i]=0;
}//多组数据初始化
for(int i=1;i<n;i++){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);
in[a]++;in[b]++;
}
int root=1;dfs1(root);
f[root]=size[root];
for(int i=1;i<=n;i++)visit[i]=0;//初始化
dfs2(root);ans=0;
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
printf("%d
",ans);
}
return 0;
}