HDU 5834 Magic boy Bi Luo with his excited tree

我们的路径大体有两种情况：

1. 贪心地走红色的边，不走回头路，如图

1. 走回头路，如图

   

可以看到，我们沿红边进入黄色点又离开了黄点所在子树，沿着绿边继续找路。

所以两种情况分别是进入一个点所在子树后不离开该子树根节点，一个是离开。

针对这两种情况设定状态：$f_u$ 表示进入 $u$ 所在子树后不用回到 $u$ 的最大获利，$g_u$ 表示进入 $u$ 所在子树后必须回到 $u$ 的最大获利。显然地，$f_u\ge g_u$。（下面的方程中，$v$ 是 $u$ 的儿子，$len$ 是 $u$ 和 $v$ 之间这条边的边权）。

$$g_u=\sum \max(g_v-2\cdot len,0)$$

$f_u=\sum \max(g_v-2\cdot len,0)+\max[\max(g_v-2\cdot len,0)-\max(f_v-len,0)]$​​​

由于题目要求以每个点为出发点的最大获利，所以考虑换根。

如图，如果我们要算红色点为出发点的最大利润。

在原图中，红色点所在子树只有三个点，但如果将根换为红色点后紫色点变为了红色点的儿子，因此我们要先计算出以紫色点为出发点，不经过红色点所在子树可获最大利润。

如果计算出了以紫色点为出发点，不经过红色点所在子树，需要回到紫色点 可获最大利润 $g2$​，以紫色点为出发点，不经过红色点所在子树，不需要回到紫色点 可获最大利润 $f2$，我们只需要按照原来的 dp 方程更新红色点的答案即可。

而紫色点 $f2,g2$​ 的值又需要依赖根节点的 $f2,g2$​（根节点的 $f2,g2$​ 分别指以根为出发点，不经过紫色点所在子树，不需要回到根点可获最大利润 $g2$​，以根为出发点，不经过紫色点所在子树，需要回到根可获最大利润），所以我们的换根其实要通过一次 dfs 来进行。

$f2,g2$ 在知道了根节点的 $f2,g2$ 后是可以快速求出的，只需要用根节点的 $f2,g2$ 更新，然后排除红色点的原 $f,g$ 贡献即可。

怎么排除贡献呢，$g$ 的式子是一个 $\sum$ 直减就排除了，$f$ 的式子有个 $\max$，需要对于每个点记录这个 $\max$ 的最大值和次大值，以及在哪个儿子去到了最大值和次大值，然后就可以排除贡献了。

#include <cstdio>

inline int max(const int x, const int y) {return x > y ? x : y;}
struct Edge {int to, nxt, w;} e[200005];
int a[100005], head[100005], fa[100005], tot;
int f[100005], g[100005], gg[100005], son[100005][2], mx[100005][2];
int Ans[100005], w[100005];
inline void AddEdge(int u, int v, int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}
inline void upd(int u, int v, int tmp) {
	if (tmp > mx[u][0]) {
		mx[u][1] = mx[u][0], son[u][1] = son[u][0];
		mx[u][0] = tmp, son[u][0] = v;
	} else if (tmp > mx[u][1]) mx[u][1] = tmp, son[u][1] = v;
}
void dfs(int u) {
	int tmp;
	for (int i = head[u]; i; i = e[i].nxt) if (e[i].to != fa[u]) {
		int v = e[i].to;
		fa[v] = u, w[v] = e[i].w, dfs(v);
		g[u] += max(g[v] - 2 * e[i].w, 0);
		f[u] += max(g[v] - 2 * e[i].w, 0);
		upd(u, v, max(f[v] - e[i].w, 0) - max(g[v] - 2 * e[i].w, 0));
	}
	f[u] += a[u] + mx[u][0], g[u] += a[u];
}

void dfs2(int u) {
	for (int i = head[u]; i; i = e[i].nxt) if (e[i].to != fa[u]) {
		int f2 = 0, g2 = 0, ans = 0, tmp = 0, v = e[i].to;
		g2 = g[u] - max(g[v] - 2 * e[i].w, 0);
		if (son[u][0] == v) f2 = f[u] + mx[u][1] - max(f[v] - e[i].w, 0);
		else f2 = f[u] - max(g[v] - 2 * e[i].w, 0);
		ans = f[v] + max(g2 - 2 * e[i].w, 0), g[v] += max(g2 - 2 * e[i].w, 0);
		tmp = max(f2 - e[i].w, 0) - max(g2 - 2 * e[i].w, 0);
		ans -= mx[v][0];
		upd(v, u, max(f2 - e[i].w, 0) - max(g2 - 2 * e[i].w, 0));
		ans += mx[v][0];
		Ans[v] = f[v] = ans, dfs2(v);
	}
}

int main() {
	int T, kase = 0;
	scanf("%d", &T);
	while (T --) {
		tot = 0;
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
		for (int i = 1; i <= n; ++ i)
			f[i] = g[i] = head[i] = mx[i][0] = mx[i][1] = son[i][0] = son[i][1] = 0;
		for (int i = 1; i < n; ++ i) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			AddEdge(u, v, w), AddEdge(v, u, w);
		}
		dfs(1);
		for (int i = 1; i <= n; ++ i) gg[i] = g[i];
		printf("Case #%d:\n%d\n", ++ kase, f[1]);
		dfs2(1);
		for (int i = 2; i <= n; ++ i) printf("%d\n", Ans[i]);
	}
	return 0;
}