⌊ \lfloor ⌊ 从朴素到根号分治，从根号分治到树剖 ⌉ \rceil ⌉

Div.1 D的神仙题 😃

Solution

Subtask 1: n , q ≤ 5000 n,q≤5000 n,q≤5000

对于一次操作，我们分别处理树上的每个节点。定义 f u , v f_{u,v} fu,v​表示将 u u u这个节点删去后，树上分裂出的子树中，包含 v v v的那颗子树的大小。

根据期望的定义，珂以发现对于一个节点 u u u，它的期望点权增长了 n − f ( v , u ) n \frac {n-f(v,u)} n nn−f(v,u)​。换句话说，如果 u u u与 r r r在同一棵子树中，那么就无法满足要求，否则就满足要求。

大概推一下式子，我们可以只处理 f u , v f_{u,v} fu,v​的问题，对于前面的 n − n- n−，我们可以在询问的时候用之前操作的次数乘上 n n n来减去一下，对于分母，我们可以在询问的时候乘上一个 n n n的逆元。

对于每一次操作，我们分别对每一个节点的期望点权进行修改；询问的时候 O ( 1 ) O(1) O(1)查询即可。时间复杂度 O ( q n ) O(qn) O(qn)。

Subtask 2: n , q ≤ 1 0 5 n, q≤10^5 n,q≤105, 每个节点的度数不超过 10 10 10

此时，我们可以使用 d f s dfs dfs序套树状数组维护差分大力维护子树的修改操作。

由于每个节点的度数不超过 10 10 10，时间复杂度是 O ( q × 10 l o g n ) O(q×10logn) O(q×10logn)。

Subtask 3: n , q ≤ 1 0 5 n,q≤10^5 n,q≤105, 无特殊限制

可以发现，这个思路本身已经无法优化了，也很难通过换用更高级的数据结构来维护。此时，我们观察一下 S u b t a s k   1 Subtask\ 1 Subtask 1中的思路，可以发现，一次操作的代价远远高于一次询问的代价，导致两个复杂度严重不平均。现在，我们要套路地牺牲查询的复杂度来降低操作的复杂度，使得这两种复杂度大致平均。

我们仍然使用 d f s dfs dfs序套树状数组维护差分来搞。但是，如果一个节点的度数过多，而每次操作的都是这个节点，那不就完了……我们必须要优化这一步骤。即，如果操作的 v v v是一个度数超过 n \sqrt n n ​的节点，直接 O ( 1 ) O(1) O(1)打上一个标记；如果度数不超过，就直接修改。对于一次查询，我们还要关注一下所有度数过大的节点的标记，否则无法正确求出这个节点的期望点权。

为什么这个算法的时间复杂度是正确的呢？因为，度数超过 n \sqrt n n ​的节点级别为 n \sqrt n n ​个，每次询问的复杂度是 O ( n ) O(\sqrt n) O(n ​)。对于一次修改，我们仍然采用原来的方法。

最劣情况的时间复杂度是 O ( n n l o g n ) O(n \sqrt {n log n}) O(nnlogn ​)。根号分治牛逼！

Subtask 4: n , q ≤ 5 × 1 0 5 n, q≤5×10^5 n,q≤5×105，无特殊限制

我们采用根号分治优化了暴力解法。现在，我们考虑换一种思想——使用树剖来优化到 O ( q l o g n ) O(qlogn) O(qlogn)。

众所周知，我们在学树剖的时候，了解到了一个神奇的性质: ⌊ \lfloor ⌊ 一个节点往上跳链的时候，跳到的轻儿子的个数不会超过 log ⁡ n \log n logn ⌉ \rceil ⌉。

大概证明一下：

可以发现：对于一个节点 i i i的所有孩子的子树大小 s i z e s o n size_{son} sizeson​中，如果存在一个 s i z e s o n ≥ n / 2 size_{son}≥n/2 sizeson​≥n/2，那么这个孩子节点就一定是重孩子。

所以，所有轻儿子的子树大小不会超过其父亲节点的子树大小的一半；即，若从一个节点向下走，每走过一个轻儿子子树大小就会至少除以 2 2 2；所以，最多经过了 log ⁡ n \log n logn条轻边，那么往上跳链同理最多只会有 log ⁡ n \log n logn条重链。

所以树剖的复杂度是 O ( log ⁡ n ) O(\log n) O(logn)。

证毕。

我们考虑这么干：对于一次操作，我们将它的重儿子做区间修改，对它的外子树作一次区间修改，其他的区间修改啥也别做。同时，在这个节点自己这里打上一个标记。

对于一次查询，可以发现，一个节点的一些贡献没有被累加，是因为它对于一些祖先，属于轻儿子的子树。我们采用树剖的思想向上跳链，由于一条重链的链头是轻儿子，那么我们就累加一下链头的父节点的标记即可。

可以发现，此时我们只需要区间修改与单点查询(询问的时候，查询一个节点在一个祖先的重儿子的子树中的贡献)，仍然可以采用 d f s dfs dfs序套树状数组维护差分来维护一下。

放几张图：

这里红色的节点是一次操作中的参数 v v v。

我们要对这些子树/外子树进行区间修改，即被标绿的部分：

对于一次查询，

根据树剖的时间复杂度，本题的总时间复杂度是 O ( q l o g n ) O(qlogn) O(qlogn)。本题得到完美解决。

树剖牛逼！

Code

咕咕咕

总结

⌊ \lfloor ⌊ 从朴素到根号分治，从根号分治到树剖 ⌉ \rceil ⌉

可以说，这是一道大套路题，需要你的积累。你会就是会，你不会就是不会。

妙哉！