Ynoi 做题笔记（2024 年暑假）

P9992 [Ynoi Easy Round 2024] TEST_130

之前大概想出来了，但是没想清楚。

发现每次询问 \(w, d\) 就相当于算 \(w\) 子树里离 \(w\) 距离不超过 \(d\) 的点的贡献之和，\(w\) 的贡献是 \(d + 1\)（因为 \(N(w, 0), N(w, 1), \ldots, N(w, d)\) 都可以），\(w\) 往下第一层的每个点分别的贡献是 \(d\)，第二层每个点分别的贡献是 \(d - 1\)，以此类推。

处理有根树的子树信息，因为有根所以我不会用点分治做这道题，因此考虑 dsu on tree 或者类似的在树上做启发式合并的做法，发现直接算不是很好算。如果每个点的贡献是它到当前子树根的距离就可以方便地做 dsu on tree 或者类似的东西了，因为这样单点的贡献和 \(d\) 无关，而且每次往上移动的时候原来子树里面所有点到当前子树根的距离都会 \(+ 1\)，很好维护。

发现容易转化到上面这种好做的题，相当于对一个询问总的贡献就是 \(w\) 子树里离 \(w\) 距离不超过 \(d\) 的点的个数 \(\times (d + 1)\)，再减去这些点到 \(w\) 的距离之和。

那么现在有两个问题：

1. 求 \(w\) 子树里离 \(w\) 距离不超过 \(d\) 的点的个数。
2. 求 \(w\) 子树里离 \(w\) 距离不超过 \(d\) 的点到 \(w\) 的距离之和。

我之前、刚才想得好像有点问题！dsu on tree 做这个好像是双 log 的，可能可以用平衡树。那好像还不如直接平衡树启发式合并（？？？）。

然后貌似还可以线段树合并，应该是单 log 的，但看讨论区说常数大。

另外有一个要注意的点，题目有点小瑕疵，给的 d 是可以大于子树深度的，但 d' 是不能大于子树深度的，然而数据范围里没有这个限制。[如果用上面的方法好像要注意 d 和子树深度什么的取 min。]（？）

题解区好像有在 DFS 序上跑扫描线用树状数组维护的方法。还没仔细看。