CodeForces 633F The Chocolate Spree（树形DP）

CodeForces 633F The Chocolate Spree（树形DP）"/>

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;
}