cf633F. The Chocolate Spree(树形dp)
2024-08-28 02:37:43
题意
\(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];
}
/*
*/
最新文章
- Gradle 刷新依赖
- assets 加载资源文件
- Sql Server插入数据并返回自增ID,@@IDENTITY,SCOPE_IDENTITY和IDENT_CURRENT的区别
- 关于Lucene 3.0升级到Lucene 4.x 备忘
- Lucene Field
- 【转】Android开发学习笔记:5大布局方式详解
- linux shell if参数
- 【html】【16】高级篇--毛玻璃效果[模糊]
- Js/Jquery- Base64和UrlEncode编码解码
- shell 编程之 if...else case...esac
- BestCoder Round #34_1002 以及 hdu 5191
- Android app性能测试小结(7个性能指标)
- 201621123050 《Java程序设计》第3周学习总结
- bzoj千题计划251:bzoj3672: [Noi2014]购票
- C# web项目利用docx文档作为模板~为打印专做的解决方案
- LR单用户,重复操作日志
- IDEA 运行spring boot出现端口占用的问题
- Typescript学习笔记(五) 模块机制
- Codeforces.209C.Trails and Glades(构造 欧拉回路)
- 面向对象编程之Java多态
热门文章
- 搜索【洛谷P2845】 [USACO15DEC]Switching on the Lights 开关灯
- kuangbin专题十六 KMP&;&;扩展KMP HDU2609 How many (最小字符串表示法)
- virturalenv 虚拟环境
- 使用esp32-Arduino+PubSubClient+mqtt 上传数据到中移动OneNet
- php 伪造HTTP_REFERER页面URL来源的三种方法
- C#中web项目使用log4net日志
- css过渡transition
- linux / OS 杀死进程
- C:foreEach
- 8	Operator overloading