CodeForces 633F The Chocolate Spree（树形DP）

题意：给出一棵树，每个节点有一个权值，求出不相交的两条链的最大权值和。

思路：树形DP。

可以发现一棵树的两条链一共会出现以下七种情况，七种情况又可以进一步划分成四种情况

f[u][0] 表示以u为根的子树中最长的两条链之和

f[u][1] 表示以u为根的子树中最长的一条链

g[u] 表示以u为根的子树中从u到叶子节点加上另外一条链的最长长度

h[u] 表示以u为根的子树中儿子节点中f[son][1]的最大值

down[u] 表示从u到叶子节点的最长长度

然后在dfs的过程中进行递推即可。

#include<bits/stdc++.h>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int MAXN = 100100;
//const int INF = 0x3f3f3f3f;
int n;
vector<int> G[MAXN];
int w[MAXN];
/*
*f[u][0] 表示以u为根的子树中最长的两条链之和
*f[u][1] 表示以u为根的子树中最长的一条链
*
*g[u] 表示以u为根的子树中从u到叶子节点加上另外一条链的最长长度
*h[u] 表示以u为根的子树中儿子节点中f[son][1]的最大值
*down[u] 表示从u到叶子节点的最长长度
*/
LL f[MAXN][2], g[MAXN], h[MAXN], down[MAXN];
void dfs(int cur, int fa) {
	f[cur][0] = w[cur];
	f[cur][1] = w[cur];
	g[cur] = w[cur];
	h[cur] = 0;
	down[cur] = w[cur];
	for (int i = 0; i < G[cur].size(); i++) {
		int u = G[cur][i];
		if (u == fa) continue;
		dfs(u, cur);
		
		//一共四种情况
		f[cur][0] = max(f[cur][0], f[u][0]);
		f[cur][0] = max(f[cur][0], f[cur][1]+f[u][1]);
		f[cur][0] = max(f[cur][0], down[cur]+g[u]);
		f[cur][0] = max(f[cur][0], g[cur]+down[u]);

		//一共两种情况
		f[cur][1] = max(f[cur][1], f[u][1]);
		f[cur][1] = max(f[cur][1], down[cur]+down[u]);

		g[cur] = max(g[cur], w[cur]+g[u]);
		g[cur] = max(g[cur], down[cur]+f[u][1]);
		g[cur] = max(g[cur], down[u]+w[cur]+h[cur]);

		h[cur] = max(h[cur], f[u][1]);

		down[cur] = max(down[cur], down[u]+w[cur]);
	}
}
int main()
{
    //freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1, 0);
	printf("%I64d", f[1][0]);
    return 0;
}