codeforces 633F The Chocolate Spree

codeforces 633F The Chocolate Spree"/>

codeforces 633F The Chocolate Spree

题意：

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

题解：

To Be Honest，我没有一点思路，也不知道为什么要维护这么多值，太弱辣~仅仅是看的懂而已QAQ

解释一下代码：

mt[u] 表示以u为根的子树中两条链最大的权值

mo[u] 表示以u为根的子树中一条链最大的权值

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

h[u]表示以u为根的子树中，最大的mo[u]

down[u] 表示以u为根的子树中，从u到叶子节点最长的一条链的权值

代码：

#include <bits/stdc++.h>
using namespace std;#define LL long long
const int N = 3e5 + 7;
vector <int> e[N];
int n;
LL mo[N], mt[N], g[N], h[N], down[N], w[N];void Dfs (int u, int pre) {mt[u] = w[u];mo[u] = w[u];g[u] = w[u];h[u] = 0;down[u] = w[u];for (int i = 0; i < e[u].size(); ++i) {int v = e[u][i];if (v == pre) continue;Dfs (v, u);mt[u] = max (mt[u], mt[v]);mt[u] = max (mt[u], mo[u] + mo[v]);mt[u] = max (mt[u], down[u] + g[v]);mt[u] = max (mt[u], g[u] + down[v]);mo[u] = max (mo[u], mo[v]);mo[u] = max (mo[u], down[u] + down[v]);g[u] = max (g[u], g[v] + w[u]);g[u] = max (g[u], down[u] + mo[v]);g[u] = max (g[u], down[v] + w[u] + h[u]);h[u] = max (h[u], mo[v]);down[u] = max (down[u], down[v] + w[u]);}
}int main () {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);e[u].push_back(v);e[v].push_back(u);}Dfs (1, 0);cout << mt[1] << endl;return 0;
}

总结：

还需要仔细想想为什么维护这些值啊，弱鸡一个QAQ

转载于:.html