[GXOI/GZOI2019]旧词

Link

Description

给定 (Q) 个询问和常数 (k)，每次询问给定 (x,y)，求

[sum_{ileq x} dep[lca(i,y)]^k ]

Solution

和 LCA 很像，只差了一个 (k) 次方的区别。

还是考虑之前的做法。我们需要构造权值，使得公共前缀的权值和是深度的 (k) 次方。那么当前前缀，和短一的前缀差分，就得到了该点权值，即

[dep[u]^k-(dep[u]-1)^k ]

同样树剖维护即可。