P5305 [GXOI/GZOI2019] 旧词

非常好差分题。

$k=1$ 时就是 P4211 [LNOI2014] LCA，将询问离线下来并拆成两半，对于贡献点将其到根节点路径上的边都加上 $1$，询问点答案就是其到根节点的边权值和。

思考 $k>1$ 咋做。我们仿照上述方法，对于连接 $(x,fa_x)$ 的边，给它加上 $dep_x^k-(dep_x-1)^k$，询问点与贡献点路径会在 LCA 相遇，于是就是 LCA 深度答案的差分数组的前缀和。