POJ3585

POJ3585

题意

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

思路

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

$d$d数组表示该点的最大水流量， $f$f数组表示一该点为根的答案， $deg$deg为度数。


当节点由 $fa$fa转移到 $x$x时， $f\left[x\right]$f[x]分为两个部分，其中一个部分是 $d\left[x\right]$d[x],另一个部分为与 $fa$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;
}