关系树 题解

· · 题解

upd on 2021.10.2: 修复了代码的问题。

upd on 2021.1.31: 修改了对 Subtask 3 做法的描述。

题外话

这题第二部分做法来自某次校内模拟赛，出题人对其进行了一定的改动。

题意

给定一棵树，定义数对 (a,b) 合法当且仅当对于所有序号在 a,b 之间的点构成的顶点导出子图中不存在一条路径长超过 k 的路径。每次询问 (l,r)，求满足 l \leq a\leq b\leq r 且合法的 (a,b) 对数及所有的 b-a+1 之和。

可以证明，如果 (a,b) 不合法，那么 (a-1,b) 和 (a,b+1) 一定也不合法。

假设我们已经求出对于所有的 a 最小的不合法的 b，即为 rq[a]。根据上面的性质，可以发现 rq 刚好构成一条单调不下降序列。

对于每个询问 (l,r)，可以分成 rq[i]\leq r 和 rq[i]>r 两部分处理。因为有如上性质，可以发现两部分刚好是连续的。

第一部分可以利用前缀和优化，第二部分因为存在规律，可以根据长度直接推公式。

每个询问处理复杂度为 O(\log n)（二分寻找两部分分割点）。

考虑如何求 rq。

容易得到下面的思路：

在树上找出所有长度为 k+1 的路径，假设该路径序号最小的点序号为 a，序号最大的点序号为 b。则 rq[a] 应为所有的 b 中的最小值。全部统计完以后再从后往前取最小值即可得到 rq。

伪代码如下：

void ss()//找路 
{
    找到一条路
    rq[a]=min(rq[a],b);
}
int main()
{
    for(int i=1;i<=n;i++)rq[i]=n+1;
    不断找路
    for(int i=n-1;i>0;i--)rq[i]=min(rq[i],rq[i+1]);
}

Subtask 1：

枚举路径起点暴力 dfs 即可。

复杂度 O(n^2)。

Subtask 2：

既然是链肯定有一些性质。出题人懒得写了。

Subtask 3：

对于两条长度都为 k+1 的路径，假设第一条路径中序号最小和最大的点序号分别为 a,b，另一条为 c,d，如果 c \leq a 且 d \geq b，那么可以不考虑第二条路径，从而减少枚举数量。

考虑点分治。

用平衡树记录每层以根为一个路径端点的路径长为 l 的所有路径中序号最大和最小的点的序号（假设为 p,q），并利用如上性质维护（如果存在另一个长度相同且所包含点的区间被其包含，那么就可以将这条路径从平衡树中删除）。此时平衡树内的两个序列都是单调递增的。对于每次 dfs 得到的路径，显然最后组合出的长为 k+1 的路径所包含点的区间必然包含 \left[p,q\right]，因此只需要在平衡树内找到所有长度为 k+1-l 的路径中最小点序号大于 p 且最小的路径（即 p 的后继）和最大点序号小于 q 且最大的路径（即 q 的前驱），让之前 dfs 得到的路径与分别与这两条拼接即可。而对于其中所包含点的区间包含 \left[p,q\right] 的长度为 k+1-l 的路径，可知其组出的区间已经达到最优，因此可以直接将其从平衡树内删除。

总复杂度为 O(n\log^2n)，常数略大。

代码（略长，但其中很多都是板子）：