题目描述

给定一个 $n$ 个点的树。

称一条树边 $(u,v)$ 关于区间 $[l,r]$ 是好的，当且仅当存在 $l\le i<j\le r$，使得编号 $i,j$ 的点在树上的简单路径经过了 $(u,v)$。

定义一个区间 $[l,r]$ 的权值为关于 $[l,r]$ 好的树边数量。

有 $q$ 次询问，每次询问给出 $l,r$，你需要回答满足 $l\le i<j\le r$ 的所有区间 $[i,j]$ 的权值和。

对于 $100\%$ 的数据，满足 $1\le n,q\le 10^5,1\le u,v\le n,1\le l\le r\le n$。

题目解法

考虑 $(u,fa_u)$ 关于 $[l,r]$ 好的条件，转化为 $u$ 子树内有 $[l,r]$ 之间的点且 $u$ 并不是 $\operatorname{lca}(l,l+1...r)$ 本身或其祖先，其中后面条件可以容斥掉，只需要减去询问区间的所有子区间 $\operatorname{lca}$ 深度和即可。

现在计算单个区间权值转化为两个问题：区间 $\operatorname{lca}$ 深度，有多少个子树内有该区间之间的点。

• 区间 $\operatorname{lca}$ 深度。

即解决询问区间子区间 $\operatorname{lca}$ 深度和，考虑扫描右端点，维护所有左端点对应 $\operatorname{lca}$ 深度，并维护历史和。

对于一个当前的右端点 $r$，其所有左端点的对应 $\operatorname{lca}$ 一定在一条链上，那么加入 $r+1$ 时，将 $r+1$ 与这条链的最低点也就是 $r$ 取 $\operatorname{lca}$，将那些比这个 $\operatorname{lca}$ 还深的对应 $\operatorname{lca}$ 都改成这个 $\operatorname{lca}$，更浅的不变，可以直接实现区间覆盖区间历史和，也可以每次暴力修改一段左端点区间的对应 $\operatorname{lca}$，实现区间加区间历史和，修改次数均摊线性。这一部分是 $O(n\log n)$ 的。

• 有多少个子树内有该区间之间的点

考察一个点 $u$ 不计入 $[l,r]$ 答案的时候，将 $u$ 子树内点按编号排序，那么这个 $[l,r]$ 一定是介于两个编号排序后相邻的点之间的，可以抽象成矩形加。

考虑树上启发式合并，对每个子树维护一个 set 或一棵平衡树之类，内部存子树内点的编号，每次把小子树的某点合并到大子树里的时候，将大子树对应平衡树中该点编号前驱后继取出，并将这个矩形加终止，换用新的两个矩形加。

问题变为 $O(n\log n)$ 次矩形加，询问即为矩形查询，可以在 $O(n\log^2 n)$ 的时间内得到解决。

综上，整个问题在 $O(n\log^2 n)$ 的时间内得到解决。