Description：

给出一棵以 $1$ 为根的树，每次给出一个二元组 $(u,k)$ ，询问三元组 $(u,b,c)$ 的个数： $u,b,c$ 均 不同，且 $u,b$ 均为 $c$ 的祖先， $u,b$ 的距离不超过 $k$ 。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

1、 $b$ 是 $u$ 的祖先， $b$ 有 $\min(k,dep[u]-1)$ 种选法， $c$ 有 $siz[u]-1$ 种选法，答案就是 $\min(k,dep[u]-1)\times(siz[u]-1)$ 。显然可以 $O(1)$ 计算。

2、 $b$ 不是 $u$ 的祖先，则 $b$ 满足 $b\in subtree(u),dep[b]-dep[u]\leqslant k$ 并且贡献为 $siz[b]-1$ ，显然是一个二维数点问题可以用主席树解决。

Code：

没有代码