题解：P5305 [GXOI/GZOI2019] 旧词

· · 题解

提供一个点分树题解，可以做到在线 O((n+q)\log^2n) 或离线 O((n+q)\log n)。

先对原树建出点分树，假设有询问 x,y，设当前在点分树上跳到节点 u。

若原树中 y 在 u 子树内：则点分树 u 子树内除 y 子树的其他节点 v 造成的贡献为 \sum \operatorname{depth}(\operatorname{lca}(v,u))^k，这个东西可以预处理。

否则，点分树 u 子树内除 y 子树的其他节点 v 造成的贡献为 \sum \operatorname{depth}(\operatorname{lca}(y,u))^k，即只需统计 v 的数量然后乘上固定的贡献系数即可，同样容易预处理。

提交记录