NC51180_牛客博客

题意

给定一棵 $n$ 个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。

思路

换根DP
这种题往往都是先从某个点出发 $DFS_1$ ，求出以这个节点 $t$ 为根的答案，并记录与答案相关的数据到数组中。
然后 $DFS_2$ 从 $t$ 节点出发，记录换根的答案，其中所有根的最大值就为所求值。
难点在于该如何去找寻其中的递推关系式。

$d$ 数组表示该点的最大水流量， $f$ 数组表示一该点为根的答案， $deg$ 为度数。
图片说明
当节点由 $fa$ 转移到 $x$ 时， $f[x]$ 分为两个部分，其中一个部分是 $d[x]$ ,另一个部分为与 $fa$ 节点相连的部分。
注意：要对fa节点是否为根节点进行讨论。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int n;
ll d[N],f[N],ans;
vector<pair<int,int> > G[N];

void dp(int x,int fa){
    for(auto c:G[x]){
        ll u=c.first,v=c.second;
        if(u==fa) continue;
        dp(u,x);
        if(d[u]!=0) d[x]+=min(d[u],v);
        else d[x]+=v;
    }
}

void dfs(int x,int fa,ll v){
    if(fa!=-1){
        f[x]=d[x];
        if(G[fa].size()!=1) f[x]+=min(f[fa]-min(d[x],v), v);
        else f[x]+=v;
    }
    for(auto c:G[x]){
        ll u=c.first,p=c.second;
        if(u==fa) continue;
        dfs(u,x,p);
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) G[i].clear(),d[i]=0,f[i]=0;
    for(int i=1;i<n;i++){
        int u,v,w;cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dp(1,-1);
    f[1]=d[1];
    dfs(1,-1,G[1][0].second);
    cout<<*max_element(f+1,f+1+n)<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}