https://ac.nowcoder.com/acm/problem/51180

Description

给你一颗有 个节点的树，每一条边连接 和 ，流量为 ，你需要找出一个点作为 ，并最大化从该点出发到所有叶子节点的流量最大值。
多组数据。（PS：题意读不懂的可以结合题目中的图理解，类似网络流的流法）
数据范围 ，并且
时间限制

Solution

我们先默认这棵树以 为根，跑一次 。
定义 表示以 为根的子树中流量最大值。
那么， 节点从儿子 得到的流量为：
1.若为叶子节点，那么（可以直接流过来）；
2.若为非叶子节点，那么（和相连的边有流量限制）。
这样，我们得到了以 为根时的答案，记为 ，它的值等于 。
考虑如何换根。
从 为根转移到儿子 为根， 包括两部分：一部分是从 流向自己的子树，一部分是从 往父节点走。
那么贡献的变化是第二部分造成的，原本的贡献是 ，现在加上 到 这条边的流量限制，所以新的贡献是 。
注意如果 的度为 ，则需要特殊处理。
再来一个 转移即可。
复杂度 ，可以通过本题。

Code

#include <cstdio>
#include <vector>
#include <memory.h>
using namespace std;
const int maxn=2e5+10;

int n,rt,d[maxn],f[maxn],deg[maxn];
struct node{
    int to,w;
    node(int x=0,int y=0):to(x),w(y){}
};
vector<node> G[maxn];

#define cls(a,b) memset(a,b,sizeof(a))
void init(){
    cls(d,0);cls(f,0);cls(deg,0);
    for(int i=1;i<=2e5;i++)G[i].clear();
}

inline void add_edge(int from,int to,int w){
    G[from].push_back(node(to,w)),++deg[from];
    G[to].push_back(node(from,w)),++deg[to];
}

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int from,to,w;
        scanf("%d%d%d",&from,&to,&w);
        add_edge(from,to,w);
    }
}

void dfs1(int u,int fa){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].to,w=G[u][i].w;
        if(v==fa)continue;
        dfs1(v,u);
        if(deg[v]==1)d[u]+=w;
        else d[u]+=min(w,d[v]);
    }
}

void dfs2(int u,int fa){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].to,w=G[u][i].w;
        if(v==fa)continue;
        if(deg[u]==1)f[v]=d[v]+w;
        else f[v]=d[v]+min(f[u]-min(w,d[v]),w);
        dfs2(v,u);
    }
}

void solve(){
    rt=1;
    dfs1(rt,0);
    f[rt]=d[rt];
    dfs2(rt,0);
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    printf("%d\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        init();
        read_and_parse();
        solve();
    }
    return 0;
}