题目简述
给定一棵 $n$ 个结点组成的树，每条树边有一个最大流量（正数），要求你确定一个根结点，使得从根节点到所有叶子结点的总流量最大。要求每条边实际流量不能超过其最大流量。
$n<=200000$，所有边最大流量 $z$ 满足 $1<=z<=10000$
思路
又是自己选定根节点，考虑换根 DP。
设 $f_x$ 表示从 $x$ 流向其子树的最大流量，$g_x$ 表示从 $x$ 流向整棵树的最大流量。$f$ 很好求，对于 $x$ 的儿子 $y$，是叶子的时候直接加边权，不是的时候和 $f_y$ 取最小值就可以了。
考虑 $g$ 怎么求。现在要从 $g_x$ 转移到 $g_y$，那么 $f_y$ 的流量首先可以算进去，因为这部分和祖先无关。$x$ 流向 $y$ 的部分易得是 $\min(f_y,\ w_{x→y})$，$g_x$ 减去这部分就是 $x$ 流向其他的最大流量，然后再和 $w_{y→x}$ 取最小值就行了。
值得注意的是，当某个节点只有一个儿子的时候上面这个转移是不适用的，所以可以特判一下，$g_y=f_y+w_{y→x}$。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<vector>
#define int long long
using namespace std;
const int MaxN = 200005;
int n, head[MaxN], cntEdge, f[MaxN], g[MaxN];
bool leaf[MaxN];
struct Edge{
int destination, nextEdge, value;
}edge[MaxN*2];
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void AddEdge(int u, int v, int w){
cntEdge++;
edge[cntEdge].destination = v;
edge[cntEdge].nextEdge = head[u];
edge[cntEdge].value = w;
head[u] = cntEdge;
return;
}
inline void DFS1(int x, int fa){
for(int i=head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destination;
if(y == fa) continue;
leaf[x] = false;
DFS1(y,x);
if(leaf[y]) f[x] += edge[i].value;
else f[x] += min(edge[i].value, f[y]);
}
}
inline void DFS2(int x, int fa){
for(int i=head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destination;
if(y == fa) continue;
if(g[x] == min(f[y], edge[i].value)) g[y] = f[y] + edge[i].value;
else g[y] = f[y] + min(g[x] - min(f[y], edge[i].value), edge[i].value);
DFS2(y, x);
}
}
signed main(){
n = Read();
for(int i=1; i<n; i++){
int u = Read(), v = Read(), w = Read();
AddEdge(u, v, w);
AddEdge(v, u, w);
}
memset(leaf, true, sizeof(leaf));
DFS1(1,0);
g[1] = f[1];
// printf("%lld\n", f[1]);
DFS2(1, 0);
int ans = 0;
for(int i=1; i<=n; i++)
ans = max(ans, g[i]);
printf("%lld", ans);
return 0;
}