cf633F. The Chocolate Spree(树形dp)

题意

题目链接

\(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\)

  1. 在\(v\)中选两条不相交的链
  2. 在不含\(v\)的节点和以\(v\)为根的子树中各选一条链
  3. down[i] + g[v] 也就是从该点和子树中分别选出半条链,再从子树内选出一条完整的链
  4. 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];
}
/*

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

3497
来自专栏Golang语言社区

AVL二叉树

AVL二叉查找树 AVL二叉查找树是一种特殊的二叉查找树,其规定 每个节点的左子树和右子树的高度差最多是1 AVL调整算法 AVL树插入一个新的节点到某个节点下...

32210
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

9217
来自专栏开发与安全

算法:图解最小生成树之普里姆(Prim)算法

我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就...

3839
来自专栏数据结构与算法

Vijos / 题库 / 输油管道问题

背景 想念car的GF,car就出了道水题! 描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道...

37211
来自专栏向治洪

算法之红黑树

红黑树(一) 原理和算法详细介 1 R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树...

2456
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3828
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3929
来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3425
来自专栏机器学习算法工程师

红黑树算法

前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

39812

扫码关注云+社区

领取腾讯云代金券