不清楚正解, 但树套树真的能过 (1800ms) 题目要求即为求满足如图所示的{a, b, p, q} 对数 即对于每一个{a, b} 都要快速求出 到 的路径上, 存在 所对应的 在 的子树里 首先想到树剖, 发现线段树维护的是一段区间内所有点的对应点在 的子树里的个数, 直接在树剖的新编号上跑树套树, 具体为在下标线段树上套一层权值线段树 (对应点编号即为值, 值域依然是下标范围。 或者理解为别的也可以, 能A就是王道) 的对应点就是 , 但可能有多个, 所以开一个 维护 子树里少标了一个 , 聪明的同学们脑补一下吧 下面是代码 本来没想着能过, 结果卡着过去了, ...
