NOI 2021 D1T1 题解

ix35 · 2021-07-27 09:31:53 · 题解

近五年 NOI 最难的 D1T1。

此前题解的做法有两种：LCT 以及转化为颜色段，但这两种做法都不是我首先想到的。

将题目里的“重儿子”称为关键儿子。

由于这题看起来就是签到题，直接上个树剖暴力维护，考虑修改时每条重链上做了什么：

链顶到当前点之间的部分（不包括当前点）的关键儿子有且仅有重儿子。

当前点：关键儿子仅有上一次的链顶（一个轻儿子）。

所以我们对每个点维护两个信息：

1. 重儿子是否是关键儿子。

2. 是否存在轻儿子是关键儿子，如果存在则记录。

一个点最多有两个关键儿子，所以 2. 中只需要记录两个。

然后修改和查询就是一些简单的线段树上区间操作，相信不用多说。

注意 LCA 父亲处的细节。

时间复杂度为 O(n\log^2 n)。