PK3585 Accumulation Degree
题目大意：
给一棵树，每条边有一个最大流量，问以哪个点为源点的流量最大，求最大流量。
solution：
能感觉出是用树形 \(\text{DP}\) 做，有一个朴素的做法：分别以每个点为根进行流水，时间复杂度 \(O(n^2)\) 。显然是不允许的，考虑下优化：
看这两个图：
以 \(1\) 作为根节点：
以 \(2\) 作为根节点：
我们发现在求完以 \(1\) 为根的 \(1\) 节点的最大流量后，以 \(2\) 为根中 \(1\) 子树是以 \(1\) 为根树的一部分，所以不用再流一遍，而是进行一些转化来更新 \(2\) 节点的最大流量。
根据刚才的思想，我们可以先以 \(1\) 节点为根，记录下 \(d_i\) 表示以 \(i\) 节点为根的子树的最大流量。设 \(f_i\) 为以节点 \(i\) 为根的最大流量（区分子树与树），对于 \(1\) 号点有 \(f_1=d_1\) （显然）。设当前节点为 \(x\) ，其父节点为 \(y\) ，转化要分两种情况讨论：
-
\(x\) 不是叶子节点（什么节点均指以 \(1\) 为根的树中），如 \(4\) 节点：
此时已知 \(f_1=24,d_4=15\) ，要求 \(f_4\) ，很显然 \(f_4\) 包含 \(d_4\) ，那么另一部分怎么求呢？先用 \(f_1\) 把 \(4\) 右侧的流量减去，应该减什么呢？其实就是 \(\min(d_4,c_{1,4})\) ，这和“流”的描述相同。此时我们就知道 \(1\) 节点向下的流量了，那么 \(4\) 节点向 \(1\) 节点流量就是 \(\min(\,1\,现在的流量,c_{1,4}\) 。
转移方程：
\[f_x=
\begin{cases}
c_{x,y} & deg_x=0\d_x+\min(f_y-\min(d_x,c_{x,y}),c_{x,y})& deg_x>0
\end{cases}\]
- \(x\) 是叶子节点，如 \(2\) 节点：
这是 \(2\) 节点的最大流量就为 \(c(1,2)\) 。
细节处理：
- 在第一遍 \(\text{dfs}\) 求 \(d\) 数组时，叶子节点的 \(d\) 应为 \(\text{INF}\) 。
- 在第二遍 \(\text{dfs}\) 求 \(f\) 数组时，叶子节点的 \(d\) 应为 \(0\) 。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e5+5,INF=0x7fffffff;
int rt,fa[N];
int hd[N],nt[N<<1],to[N<<1],cnt;LL ww[N<<1];
inline void add(int x,int y,int z){
ww[++cnt]=z,to[cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
}
int deg[N];
LL d[N],f[N],c[N],ans;
void dfs_1(int x){//求d数组
for(int i=hd[x];i;i=nt[i]){
int y=to[i];LL z=ww[i];
if(y==fa[x]) continue;
deg[x]++,fa[y]=x,c[y]=z,dfs_1(y);//c数组保存到y与x边的最大流量
d[x]+=min(d[y],z);
}
if(deg[x]==0) d[x]=INF;//度为0，d数组为INF
}
void dfs_2(int x){
if(x!=rt){//通过它的父亲来计算f数组
int y=fa[x];
if(d[x]==INF) d[x]=0;//变成0
if(deg[y]==1) f[x]=c[x];
else f[x]=d[x]+min(f[y]-min(d[x],c[x]),c[x]);
}
for(int i=hd[x];i;i=nt[i]){
int y=to[i];
if(y==fa[x]) continue;
dfs_2(y);
}
ans=max(ans,f[x]);
}
int main(){
int n; scanf("%d",&n);
for(int i=1,x,y,z;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
rt=1,fa[rt]=rt,dfs_1(rt);
ans=f[rt]=d[rt],dfs_2(rt);
printf("%lld",ans);
return 0;
}