757

牛子题 先观察询问怎么处理，因为是棵树，直接拆 \(dis\) ，有 \(dis(p_i,x)=dis[p_i]+dis[x]-2\times dis[lca]\) ，前两项很好处理，但是对于 \(dis[lca(p_i,x)],i \in [l,r]\) 比较难处理，但是可以转化成经过这条边的次数 ......

[Lnk](https://www.luogu.com.cn/problem/CF757G)。这是一个 dfs 序 + 主席树的乱搞做法。 首先把树上距离拆开，令 $\operatorname{dis}(u)$ 表示 $u$ 到根的路径长度： $$\left(\sum_{i=l}^r \operat ......

好好好。 求一个点到一个集合内点的距离和，这相当于在考虑若干条路径的长度，我们可以考虑使用点分治，建出点分树，这样每次查询时只需要对于这个点到根上的每个分治中心，找到所有经过这个中心的路径和即可。容易拆成每个点到分治中心的距离之和加上点数乘分治中心到查询点的距离，那么我们直接拿前缀和维护一下这个东西 ......