RainAir
My OI Blog
RainAir
ZROI Contest 350

B

现在有一棵树 要求对于每个点 $x$ ,求所有点到他的链的最大点权之和
$n \leq 4 \times 10^5$

题解:又是我不会的思博题。
这种题目我们可以首先考虑在链上的做法:
显然有一种基于分治的方法,但是很难扩展到树上。
所以我们考虑如果变成边权是不是好维护。。(
我们考虑定义点 $i$ 和 $i+1$ 之间的边的边权是 $max\{a_{i},a_{i+1}\}$。然后变成了求两点之间边权最大值。我们考虑将边从小到大排序,每次加入一条新边,对于边左端点的连通块,答案都会加上一个边权乘右边端点连通块的大小。右面答案贡献同理。
所以我们如果放在树上也是差不多做。可以维护处所有连通块的大小,然后每次加边相当于是一个子树加贡献操作。
我们如果直接并查集路径压缩就会自闭。我们必须要维护出树的形态。第一种情况是使用带权并查集。注意要额外减去合并时多余的贡献。
一个更简单的做法是使用重构树:这样我们直接在点上打标记就可以了

C

遇到这种删数的问题我们可以首先考虑最后一个删除的数是什么/对答案的影响。
发现如果我们钦定删除了某一个点,它的值是 $x$,那么这个点会将当前区间分裂成两个区间,并且要保证左区间删除的时候不能有一时刻最右边的点的值为 $x$,右边区间同理。
所以我们可以考虑设计出一个区间 dp:$f_{l,r,lk,rk}$ 表示删除区间 $l,r$,强制不让某一时刻的左边为 $lk$,也不让某一时刻右边为 $rk$.转移显然:
$$f_{l,r,lk,rk} = \sum_{k = l}^r \left(^{r-l}_ {k-l}\right)f_{l,k-1,lk,a_k}\times f_{k+1,r,a_k,rk}$$
总共是 $O(n^5)$ 的。
转移发现 $lk = a_{l-1},rk = a_{r+1}$,所以变成 $O(n^3)$。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/720
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ZROI Contest 350
B 现在有一棵树 要求对于每个点 $x$ ,求所有点到他的链的最大点权之和 $n \leq 4 \times 10^5$ 题解:又是我不会的思博题。 这种题目我们可以首先考虑在链上的做法: 显然有一种基于分…
扫描二维码继续阅读
2019-07-26
标签
近期评论