自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:22:13，当前版本为作者最后更新于2020-03-14 21:36:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$，常数略大。

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