题意
题目链接
(n)个节点的树,点有点权,找出互不相交的两条链,使得权值和最大
sol
这辈子也不会写树形dp的
也就是有几种情况,可以讨论一下。。
下文的“最大值”指的是“路径上权值和的最大值”
设(f[i][0])表示以(i)为根的子树中选出两条不相交的链的最大值
(f[i][1])表示以(i)为根的子树中选出一条链的最大值
(g[i])表示以(i)为根的子树中从(i)到叶子节点 加上一条与之不相交的链的最大值
(h[i])表示(max{f[son][1]})
(down[i])表示从(u)到叶子节点的最大值
现在最关键的是推出(f[i][0])
转移的时候有四种情况
设当前儿子为(v)
-
在(v)中选两条不相交的链
-
在不含(v)的节点和以(v)为根的子树中各选一条链
-
down[i] + g[v] 也就是从该点和子树中分别选出半条链,再从子树内选出一条完整的链
-
g[i] + down[v] 与上面相反。
同时(g, down)也是可以推出来的。。
做完了。。慢慢调吧
#include<bits/stdc++.h> #define chmax(a, b) (a = (a > b ? a : b)) #define chmin(a, b) (a = (a < b ? a : b)) #define ll long long using namespace std; const int maxn = 100010; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n; ll a[maxn], f[maxn][2], g[maxn], h[maxn], down[maxn]; vector<int> v[maxn]; void dfs(int x, int fa) { f[x][0] = f[x][1] = g[x] = down[x] = a[x]; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa) continue; dfs(to, x); chmax(f[x][0], f[to][0]); chmax(f[x][0], f[x][1] + f[to][1]); chmax(f[x][0], down[x] + g[to]); chmax(f[x][0], down[to] + g[x]); chmax(f[x][1], f[to][1]); chmax(f[x][1], down[x] + down[to]); chmax(g[x], g[to] + a[x]); //chmax(g[x], down[to] + f[x][1]); chmax(g[x], down[x] + f[to][1]); chmax(g[x], down[to] + a[x] + h[x]); chmax(h[x], f[to][1]); chmax(down[x], a[x] + down[to]); } } main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); cout << f[1][0]; } /* */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607191.html