Luogu4338 [ZJOI2018] 历史

题意：给出从每个点可以向上进行的 access 次数 ，问轻重边切换次数的最大值。

支持对 单点增加。

，时限 。

---

首先观察触发轻重边切换的条件，不难发现，若 的两个来自不同子树的孩子触发 access，则会有一次切换。

若单独考虑点 ，则转化为如下问题。

若共有 个子树，我们令整数 分别代表不同种类的切换。其中根属于第 种，而第 个子树中的一次切换则属于第 种。

第 个子树内的切换次数总和。

那么，整数 有 个，若相邻两个数不同则触发恰好一次切换。

• 若没有 超过半数，则答案为 。

• 若有 超过半数，则答案为 。

为了方便，我们在每个点上多挂一个点，将 次数加在挂的那个点上。这样，能完全转化为子树之间的贡献。

---

分类讨论。

超过半数是一个很强的条件。将 超过半数的的子树 设为重儿子，用重边连接，否则用轻边连接。

不难发现，从某点向上的轻链条数是 级别的。

由于点权只会增加，只有下列三种可能的情况 ：

• 的边从轻边变为重边

• 的边保持为轻边

• 原有的，不是指向 的重边断开

若 的边本为重边，则不会改变。且贡献也不变。

不难发现重链变动和一路上的轻链条数有关。

LCT 维护，复杂度 。