题目描述
C++ 代码
#include<bits/stdc++.h>
using namespace std;
// Tag: 树形DP 二次扫描与换根法
/*
树中每条边都有容量,无向边。树叶是汇点。
在树中选择一个点为树根,作为源点。
问选择哪个点作为源点,可以使得 整个水系中的流量最大。
暴力法:
对于树中的每一个点都进行一次 树形DP。
整个水系中的水的最大值一定是更结点能流出的最大流量。
我们知道,树叶能流出的水是无限的,取决于流入多少水;
而对于非树叶、非树根的分支节点,能流经这个点的最大流量等于
流入流量 和 所有子节点流出之和 的最小值。
但是,O(N)完成以某一点为根的最大值求解,求N遍,故最终复杂度为O(N^2)。
肯定TLE。
树形DP换根法:
可以在O(N)的时间内解决问题。
首先,任选一点为root,做一遍DP。
D(x)表示以x为根的子树的最大流量。
F(x)表示以x为根(源点)整棵树的最大流量。
对于root,F[root] = D[root]
假设F(x) 已经被正确求出,考虑其子节点y,
F(y) 由两部分组成:
1. 从y流向以y为根的子树 ,就是 D(y)
2. 从y流向y的父节点。
对于2:
根节点 F(x) 也由子节点和父节点流量两部分组成,但是,减去流向y的
流量之后,就是y通过x流出的所有流量。
即,2 = F(x) - min( D(y) , c(x,y) );
故,从选定的root结点开始,再向下做一遍dfs即可。
F[y] = D[y] + { min( F[x] - min( D(y), c(x,y) ), c(x,y) ) (degx>1)
{ c(x,y) (degx=1)
!!!注意!!! 度为1的时候,转移方程不同!
属性: 最大值
更一般地:
树形DP解决问题时,每一个子树都要代表一个“子问题”
然后通过子问题解决父节点的问题。
在进行换根DP时,一般需要得到每个结点的DP结果。
解法一般分成两步:
1. 第一次扫描,任选一结点为根,在有根树上进行dfs。
2. 第二次扫描,通过第一次dfs过程中记录的数据,和根节点dfs出的dp结果
寻找父节点和子节点之间的性质,并写出转移方程,
利用父节点的dp值来更新子节点的DP值。
*/
const int N = 200010;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int f[N],d[N];
int cnt[N];
int T;
int n;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs1(int u,int fa)
{
d[u]=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs1(j,u);
if(cnt[j]==1) d[u]+=w[i];
else d[u]+=min(w[i],d[j]);
}
}
void dfs2(int u,int fa)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(cnt[j]==1 && cnt[u]>1) f[j]=d[j]+min(w[i],f[u]-w[i]);
else if(cnt[j]>1 && cnt[u]>1)f[j]=d[j]+min(f[u]-min(d[j],w[i]),w[i]);
else if(cnt[u]==1) f[j]=d[j]+w[i];
dfs2(j,u);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(h,-1,sizeof h);
memset(cnt,0,sizeof cnt);
idx=0;
scanf("%d",&n);
int a=0,b=0,c=0;
for(int i=1;i<n;i++)
{
scanf("%d %d %d",&a,&b,&c);
add(a,b,c),add(b,a,c);
cnt[a]++,cnt[b]++;
}
dfs1(1,0);
f[1]=d[1];
dfs2(1,0);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,f[i]);
cout<<ans<<endl;
}
return 0;
}