当前位置：网站首页>【学习笔记】树形dp

【学习笔记】树形dp

2022-07-15 09:43:00 【仰望星空的蚂蚁】

Nearest Leaf

The Chocolate Spree

Power Tree

Pairs of Paths

sb数据结构题
暴力
分两种形态暴力
评分3000不过分吧

Nested Rubber Bands

巧妙的题目
菊花图显然是合法的
把菊花图拼起来也是合法的
手玩可以得到
若干菊花图拼起来的子图只能连一条边出去
等价于，菊花图的中心必须拼成一条链
毋宁称之为构造题
可以树形dp
注意细节
复杂度 $O (n)$

Distance Tree

巧妙的题目
假定其中一个端点是 $1$
另一个端点是 $u$
考虑二分答案 $l$
因为这样做比较顺
把 $u$ 求出来
然后考虑那些深度比 $l$ 大的叶子
把绝对值拆开就可以 $O (1)$ 判了
复杂度 $O(n\log n)$
~~vscode好评~~
不保证是正解。不保证和题解一样优秀。

Two-Paths

~~行百里者，半九十~~
对不起我又要骂了~~sb数据结构~~
倍增+暴力
$d p [u]$ 表示从 $u$ 出发遍历完子树的最大贡献
$d p 2 [u]$ 表示从 $u$ 出发遍历完整个子树的最大贡献
$d p [u], d p 2 [u]$ 是一个求和的形式
这启发我们用倍增+暴力统计答案
代码很恶心就不说了
~~vscode好评~~

版权声明
本文为[仰望星空的蚂蚁]所创，转载请带上原文链接，感谢
https://blog.csdn.net/cqbzlydd/article/details/125780433

边栏推荐

猜你喜欢

随机推荐