题解：P14509 树上求值 tree

这题感觉比较套路，但场上想了 $30$ min 开始写然后因为代码能力太差又花了一个半小时还是太菜了。

下文中定义 $S_{i}$ 为 $i$ 及其子树中点构成的集合。

注意到 $\sum f(i)$ 容易用 $01$ Trie 树整体计算，并且$f(i+d_{\operatorname{LCA*}(i,x)})$ 这样的式子里的 $d$（节点深度）在 dfs 过程中每步只会加减一，容易联想到 Trie 树全局加减，因此尝试往 $01$ Trie 这个方向想。

我们发现，一个节点的 $s$ 值可以按如下方式划分（黄点为根，红点为当前点）：

红点（编号为 $3$）的 $s$ 值即可表示为 $\sum\limits_{i \in \complement_{S_{1}} S_{2}} f(i+1) + \sum\limits_{i \in \complement_{S_{2}} S_{3}} f(i+2) + \sum\limits_{i \in S_{3}} f(i+3) = \sum\limits_{i \in S_{1}} f(i+1) - \sum\limits_{i \in S_{2}} f(i+1) + \sum\limits_{i \in S_{2}} f(i+2) - \sum\limits_{i \in S_{3}} f(i+2) + \sum\limits_{i \in S_{3}} f(i+3)$。

这个过程类似于换根，因此，我们考虑在遍历原树的时候维护每棵子树中每个点（称这个点为 $x$）的 $i+d_{x}$ 的值构成的 $01$ Trie（每个点对应的 Trie 树由孩子节点的 Trie 树全局减一然后合并，再插入自己得来），然后记录每个点的 $\sum\limits_{i \in S_{x}} f(i+d_{x})$ 以及 $\sum\limits_{i \in S_{x}} f(i+d_{x}-1)$ 的结果，最后我们就可以再跑一次 dfs 记录从根出发路径上的信息和得到每个点的 $s$ 值。

考虑到 $01$ Trie 树的插入、合并和全局减操作，每组数据时间复杂度均为 $O(n \log n)$。由于我赛时脑子坏了 $01$ Trie 树写启发式合并导致代码略为繁琐且时间复杂度较高（多带了一个 $\log$ 但是卡常卡过去了），因此不再展示。