Luogu5439 【XR-2】永恒

题意 ： 给出两棵树 ，标号对应。

定义 为 上 两点的 的深度，也简记为 。

定义 上一条路径 的价值为

求 所有无向路径的价值和，答案对 取模。

，时限 。

---

统计树上点对贡献。

考虑点分治，每次处理通过分治中心 的所有路径的贡献。

令整颗原树以 为根，设 为 点的子树大小。其求解可以借助点分治。

若 不在同一个子树内，同时经过 的路径总数即为 。

于是问题变成了：

这可以在 上建立虚树，然后树形 计算。

利用归并和 建立虚树，复杂度为 。