题解：P14509 树上求值 tree
WaTleZero_pt
·
·
题解
这题感觉比较套路，但场上想了 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 但是卡常卡过去了），因此不再展示。