poj3585【树形dp二次换根】

这道题如果用暴力的方法是枚举根节点，对每个根节点dfs下去，但是这样肯定会T，需要用树形dp优化一下。
辅助数组：d[maxn], f[manx];
d[i]：代表以任意某个节点为根，i可以向其子节点流的最大流量。
f[i]：代表以i为根节点时，最大流量。
当我们以1为根节点时，明显f[1] = d[1];

处理d【i】数组：一遍dfs就行。
关键在于如何求f【i】？

我们可以知道f[i] = d[i] + （i通向父节点的那条路最多可以流的流量）
假设i的父节点为y, y到i的通路流量为c
实际上就是min(f[y]-min(d[i], c), c)：父节点在别的子节点的流量和与c取min。

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+9;
int Case = 1;
int n, m, tot, deg[maxn], d[maxn], f[maxn], head[maxn];
struct node{
	int nex, val, to;
}node[maxn<<1];

void add(int x, int y, int v) {
	tot++;
	node[tot].nex = head[x];
	node[tot].val = v;
	node[tot].to = y;
	head[x] = tot;
}

void init() {
	for(int i = 1; i <= n; i++) {
		deg[i] = 0;
		head[i] = -1;
	}
	tot = 0;
}

void dfs1(int u, int fa) {
	d[u] = 0;
	for(int i = head[u]; ~i; i = node[i].nex) {
		int v = node[i].to, c = node[i].val;
		if(v == fa) continue;
		dfs1(v, u);
		if(deg[v] == 1) d[u] += c;
		else d[u] += min(d[v], c);
	}
}

void dfs2(int u, int fa) {
	for(int i = head[u]; ~i; i = node[i].nex) {
		int v = node[i].to, c = node[i].val;
		if(v == fa) continue;
		if(deg[u] == 1) f[v] = d[v] + c;
		else f[v] = d[v] + min(f[u]-min(d[v], c), c);
		dfs2(v, u);
	}
}

void solve() {
    scanf("%d", &n);init();
    for(int i = 1; i < n; i++) {
   		int u, v, c;
   		scanf("%d%d%d", &u, &v, &c);
   		deg[u]++;deg[v]++;
   		add(u, v, c);
   		add(v, u, c);
    }
    dfs1(1, -1);
    f[1] = d[1];
    dfs2(1, -1);
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return;
}

int main() {
	scanf("%d", &Case);
    while(Case--) {
        solve();
    }
    return 0;
}