FarmCraft
题目链接:https://lydsy.com/JudgeOnline/problem.php?id=3829
数据范围:略。
题解:
因为每条边只能必须走两次,所以我们的路径一定是进入了一棵子树然后出来,不可能再进去。
我们根据这个性质,设计出状态$f_i$表示以$i$为根的子树答案即可。
转移时,我们发现需要对儿子进行一个排序,我们就暴力的判断一下哪个儿子在前面更优即可。
代码:
#include <bits/stdc++.h> #define N 1000010 using namespace std; char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() { int x = 0, f = 1; char c = nc(); while (c < 48) { if (c == '-') f = -1; c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x * f; } int head[N], to[N << 1], nxt[N << 1], tot; inline void add(int x, int y) { to[ ++ tot] = y; nxt[tot] = head[x]; head[x] = tot; } int sz[N]; void dfs(int p, int fa) { sz[p] = 1; for (int i = head[p]; i; i = nxt[i]) { if (to[i] != fa) { dfs(to[i], p); sz[p] += sz[to[i]]; } } } int t[N], f[N]; struct Node { int val, id; }q[N]; // inline bool cmp(const Node &a, const Node &b) { // return a.val < b.val; // } inline bool cmp(const Node &a, const Node &b) { return max(a.val, sz[a.id] * 2 + b.val) < max(b.val, sz[b.id] * 2 + a.val); } void dfs1(int p, int fa) { f[p] = t[p]; for (int i = head[p]; i; i = nxt[i]) { if (to[i] != fa) { dfs1(to[i], p); } } int cnt = 0; for (int i = head[p]; i; i = nxt[i]) { if (to[i] != fa) { q[ ++ cnt] = (Node) {f[to[i]], to[i]}; } } sort(q + 1, q + cnt + 1, cmp); int sum = 0; for (int i = 1; i <= cnt; i ++ ) { f[p] = max(f[p], f[q[i].id] + sum + 1); sum += sz[q[i].id] * 2; } } int main() { int n = rd(); // int m = t[1]; for (int i = 1; i <= n; i ++ ) { t[i] = rd(); } // t[1] = 0; for (int i = 1; i < n; i ++ ) { int x = rd(), y = rd(); add(x, y), add(y, x); } dfs(1, 1); dfs1(1, 1); // for (int i = 1; i <= n; i ++ ) { // printf("%d ", f[i]); // } // puts(""); cout << max(f[1], (n - 1) * 2 + t[1]) << endl ; return 0; }