NC51180 Accumulation Degree

题意

给定一颗 个点 条边的树，每条边有一个最大流量 。选择一个点为根，使得根到叶子节点的流量和最大，求最大值。（一条路径的流量指叶子节点到根节点的边权最小值）

分析

先以 号点为根节点，那么很容易得到从一个点出发的流量（是儿子节点）：
接下来考虑不以 为根。设 表示以 为根的流量和。

那么考虑从 到 的转移。
让我们从这个图看看以 为根时， 的流量来源。
首先是 ，就是一开始求的。
然后还有红色箭头标出来的部分，流经 这条边，流量其实就是。
现在我们要知道，红色部分怎么得到。
从这个图可以看到，红色部分其实就是用 减去 。
从上面的推理，那么我们可以得到：
最后 即可。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 100005
#define inf 1e15
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
struct node{
    int a, b, c, n;
}d[N * 2];
int h[N], fa[N], siz[N], cnt;
LL f[N], g[N];
void cr(int a, int b, int c){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b, c;
    siz[a] = 1;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b; c = d[i].c;
        if(b == fa[a]) continue;
        fa[b] = a;
        dfs(b);
        siz[a] += siz[b];
        if(siz[b] != 1) f[a] += min(f[b], z * c);
        else f[a] += c;
    }
}
void dfs1(int a){
    int i, b, c;
    LL t;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b; c = d[i].c;
        if(b == fa[a]) continue;
        t = g[a] - min(f[b], z * c);
        g[b] = f[b] + min(t, z * c);
        dfs1(b);
    }
}
int main(){
    int i, j, n, m, T, a, b, c;
    LL ans;
    T = read();
    while(T--){
        n = read();
        cnt = 0; ans = 0;
        for(i = 1; i <= n; i++) h[i] = f[i] = g[i] = fa[i] = 0;
        for(i = 1; i < n; i++){
            a = read(); b = read(); c = read();
            cr(a, b, c);
            cr(b, a, c);
        }
        dfs(1);
        g[1] = f[1];
        dfs1(1);
        for(i = 1; i <= n; i++) ans = max(ans, g[i]);
        printf("%lld\n", ans);
    }
    return 0;
}