题解

思路

记结点 $u$ 的深度为 $dep_u$，子树大小为 $sz_u$。固定询问中的 $a=p$ 后，$c$ 必须是 $p$ 的真后代。因为 $a,b$ 都是 $c$ 的祖先，所以 $a,b$ 一定位于同一条根到 $c$ 的路径上。

结点 $b$ 有两类。

第一类是 $p$ 的真祖先。距离 $p$ 不超过 $k$ 的这类结点共有 $\min(k,dep_p-1)$ 个，每个都能和 $p$ 子树内任意真后代 $c$ 配对，因此贡献

$$(sz_p-1)\min(k,dep_p-1).$$

第二类是 $p$ 的真后代。若 $dep_b-dep_p\le k$，则 $c$ 可以是 $b$ 的任意真后代，共有 $sz_b-1$ 种。因此还需统计

$$\sum_{\substack{b\text{ 是 }p\text{ 的真后代}\\dep_b\le dep_p+k}}(sz_b-1).$$

两部分相加就是答案。

各子任务算法

在极小规模中，可以枚举 $b,c$，用祖先关系和深度直接检查三元组定义。

当树是一条以根为端点的链时，每个深度恰有一个结点，子树大小只由深度决定。上式的后代部分成为一段等差数列，可常数时间求和。

当所有 $k\le20$ 时，可以自底向上维护每个结点下方距离为 $1$ 到 $20$ 的各层中，所有 $sz_b-1$ 的和。每次询问至多累加二十层。

做法

对树做深度优先遍历，求出进入时间 $tin_u$ 和退出时间 $tout_u$。结点 $p$ 的真后代对应欧拉序区间 $[tin_p+1,tout_p]$。

把每个结点看作一个带权点：深度为 $dep_u$，欧拉位置为 $tin_u$，权值为 $sz_u-1$。把所有结点按深度从小到大排序，把询问按上界 $dep_p+k$ 从小到大排序。

依次处理询问，并将深度不超过当前上界的结点按欧拉位置加入树状数组。此时查询区间 $[tin_p+1,tout_p]$ 的权值和，恰好得到计数公式中的第二部分。再加上第一部分即可。

正确性说明

计数公式按 $b$ 位于 $p$ 上方或下方划分，两类互斥且覆盖所有可能的 $b$。上方的每个 $b$ 都能选择 $p$ 的任意真后代作为 $c$；下方的每个 $b$ 能选择且只能选择自身真后代作为 $c$，所以公式没有遗漏或重复。

欧拉序把一棵子树转化为连续区间。按深度离线扫描到 $dep_p+k$ 时，树状数组中恰好包含深度满足限制的所有结点，所以相应区间和等于公式的下方贡献。故算法对所有询问均正确。

复杂度

预处理和排序后，每个结点加入一次、每个询问查询一次。总时间复杂度为 $O((n+q)\log n)$，空间复杂度为 $O(n+q)$。