传送门bzoj4448

题解
离线之后构建树上主席树，每个点的线段树维护到根路径的信息，不用链剖（我的链剖只是拿来求\(\mathrm{lca}\)的），时空复杂度\(O(n\log{n})\)。

code