AcWing 287. 积蓄程度（树形dp，换根+二次扫描）

本文主要是介绍AcWing 287. 积蓄程度（树形dp，换根+二次扫描），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。

我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。

每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。

除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。

也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

输入格式
输入第一行包含整数T，表示共有T组测试数据。

每组测试数据，第一行包含整数N。

接下来N-1行，每行包含三个整数x,y,z，表示x，y之间存在河道，且河道容量为z。

节点编号从1开始。

输出格式
每组数据输出一个结果，每个结果占一行。

数据保证结果不超过231−1。

数据范围
N≤2∗105
输入样例：
1
5
1 2 11
1 4 13
3 4 5
4 5 10
输出样例：
26

思路： 太巧妙了（现在看来就是道换根裸题。。。），常规方法应该是每个点作根扫一遍。但是我们只需要扫一次，然后用这一次的信息去更新其他节点得到其他节点作为根时的结果，所以叫二次扫描。

第一个dfs是用一个点作根得到结果。第二个dfs是用上一个dfs的信息得到所有点作根的结果。
f1(i)为以i为根节点，对应子树的结果。f2(i)为以i为根节点的结果。

ACNEW NEW

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>using namespace std;
typedef long long ll;
const int maxn = 4e5 + 7;int siz[maxn],a[maxn];
int head[maxn],nex[maxn * 2],to[maxn * 2],deg[maxn],tot;
ll f[maxn],val[maxn * 2];
int n;void init() {memset(head,0,sizeof(head));memset(deg,0,sizeof(deg));memset(f,0,sizeof(f));tot = 0;
}void add(int x,int y,int z) {to[++tot] = y;nex[tot] = head[x];val[tot] = z;head[x] = tot;
}void dfs(int u,int fa) {for(int i = head[u];i;i = nex[i]) {int v = to[i];ll w = val[i];if(v == fa) continue;dfs(v,u);if(deg[v] == 1) f[u] += w;else f[u] += min(f[v],w);}
}void dfs2(int u,int fa) {for(int i = head[u];i;i = nex[i]) {int v = to[i];ll w = val[i];if(v == fa) continue;ll num;if(deg[v] == 1) {num = f[u] - w;} else {num = f[u] - min(f[v],w);}if(deg[u] == 1) {f[v] += w;} else {f[v] += min(w,num);}dfs2(v,u);}
}int main() {int T;scanf("%d",&T);while(T--) {init();scanf("%d",&n);for(int i = 1;i < n;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);deg[x]++;deg[y]++;}dfs(1,-1);dfs2(1,-1);ll ans = 0;for(int i = 1;i <= n;i++) {ans = max(ans,f[i]);}printf("%lld\n",ans);}return 0;
}

ACNEW（只是把vis打在了里面，这样做会使得点跑回来，所以要单独标记起点）

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 4e5 + 7;
int head[maxn],nex[maxn],to[maxn],val[maxn],f1[maxn],f2[maxn],tot,deg[maxn],vis[maxn];void init(int n)
{for(int i = 1;i <= n * 2;i++){head[i] = f1[i] = f2[i] = deg[i] = vis[i] = 0;}tot = 0;
}void add(int x,int y,int z)
{to[++tot] = y;val[tot] = z;nex[tot] = head[x];head[x] = tot;
}void dfs1(int x)
{f1[x] = 0;for(int i = head[x];i;i = nex[i]){int v = to[i],w = val[i];if(vis[v])continue;vis[v] = 1;dfs1(v);if(deg[v] == 1)f1[x] += w;else f1[x] += min(w,f1[v]);}
}void dfs2(int x)
{for(int i = head[x];i;i = nex[i]){int v = to[i],w = val[i];if(vis[v])continue;vis[v] = 1;f2[v] += f1[v] + min(f2[x] - min(f1[v],w),w);dfs2(v);}
}int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);init(n);for(int i = 1;i < n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);deg[x]++;deg[y]++;}vis[1] = 1;dfs1(1);f2[1] = f1[1];for(int i = 1;i <= n;i++)vis[i] = 0;vis[1] = 1;dfs2(1);int ans = 0;for(int i = 1;i <= n;i++)ans = max(ans,f2[i]);printf("%d\n",ans);}
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int maxn = 4e5 + 7;
int head[maxn],to[maxn],nex[maxn],val[maxn],deg[maxn];
int f1[maxn],f2[maxn],vis[maxn];
int tot;
int n;
void init(int n)
{for(int i = 1;i <= n * 2;i++)head[i] = 0;for(int i = 1;i <= n;i++){deg[i] = 0;vis[i] = 0;f1[i] = f2[i] = 0;}tot = 1;
}void add(int x,int y,int z)
{to[++tot] = y;nex[tot] = head[x];val[tot] = z;head[x] = tot;
}void dfs1(int u)
{vis[u] = 1;f1[u] = 0;for(int i = head[u];i;i = nex[i]){int v = to[i],w = val[i];if(vis[v])continue;dfs1(v);if(deg[v] == 1)f1[u] += w;//如果子节点的度为1，说明u和v只有一条边，f[v]无法更新，那就直接加上。else f1[u] += min(w,f1[v]);//加上子节点的最小流量或者直接加上这条边，因为是最小流量，所以只能加上其中的最小值。}
}void dfs2(int u)
{vis[u] = 1;for(int i = head[u];i;i = nex[i]){int v = to[i], w = val[i];if(vis[v])continue;if(deg[u] == 1){f2[v] = f1[v] + w;
//            cout << "hahaha "<< endl;//这一步发生的条件相当苛刻，这一句加上也能过。因为只有出现两个点一条边，才能有父节点度为1的情况。}elsef2[v] += f1[v] + min(f2[u] - min(f1[v],w),w);//x作根的流量减去y作根时的流量就等于y作根时对应x为子节点方向的流量。dfs2(v);}
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);init(n);for(int i = 1;i < n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);deg[x]++;deg[y]++;}dfs1(1);f2[1] = f1[1];for(int i = 1;i <= n;i++)vis[i] = 0;dfs2(1);int ans = 0;for(int i = 1 ;i <= n;i++){ans = max(ans,f2[i]);}printf("%d\n",ans);}return 0;
}