题解：P10107 [GDKOI2023 提高组] 树

sheepchat · 2025-08-18 15:23:55 · 题解

CSP 模拟赛（？）搬了，有同学过了，太强了。

很巧妙的题，这里介绍第一篇题解的做法。

距离是假的其实是深度之差，下面都这样认为。

考虑跑个 dfs 序，记 low_u 为子树 u 中的最大时间戳，dfn_u 为 u 的时间戳。

那么考虑这样一件事情，如果查询 (x,k)，我们会将其理解为满足 dep_u\in [dep_x,dep_x+k],dfn_u\in[dfn_x,low_x) 的点的贡献。

不妨差分一下，记 pre_u 为和 u 同层的点中，它的 dfn 序上的前驱。

满足 dep_u\in [dep_x,dep_x+k],low_{pre_u}<dfn_u\le low_x 的点的贡献，依然是没问题的，这个可以分为两段前缀，下面我们考虑求 dep_u\in [dep_x,dep_x+k],dfn_u\le low_x 点的贡献，因为这样把 x 换成 pre_x 再求一遍，一减就是答案。

（这是个典 trick 吗？我想不通为啥题解区都觉得这个很显然，问同学，同学：“做多题就知道了。”）

那么我们就转变问题了，但是 dep_u\in [dep_x,dep_x+k] 依然不好算。而且深度这一维不好做相同的操作。

那假设 k 正好是 2^p-1 呢？考虑前 2^{p-1}-1，是不变的，而且后面 2^{p-1} 相当于给他异或上 2^{p-1} 这里记下这一块有多少个 p-1 位上为 1，那么也可以计算。

欸，我们发现上面过程也可以拓展到非 2^p-1 的形式，且我们考虑记下 f_{i,x}，问题为 (x,2^i-1) 时候的答案。（不是原问题哦，而是转化完之后的）。

考虑如何去求，记 rs_u 为 u 最后遍历的儿子标号，没儿子就是 rs_{pr_u}，那么考虑类似倍增 LCA 的求解方式，同理设 rs_{i,u} 为 u \gets rs_u 这个操作重复 2^i 后的节点。