CFgym102391K Wind of Change

XX Open Cup, Grand Prix of Korea

题意：给出两棵树 ，标号对应，边有边权，均为正。

定义 为 在 中的距离， 类似。

对每个 ，求出 。

，时限 ，空限 。

---

存在点分治后建立虚树并 的做法，比较无趣，不讲。

建立 的点分树。

点分树满足一条关键性质：点分树中的 一定在原树 之间的路径中。

于是， 可以表示成 。

这有个好处，由于点分树的高度是 的，一个点的祖先数目是极少的。

那么，对每一个点 ，枚举其在点分树 上的两个祖先 ，能得到 个三元组 。

考虑如何统计答案。对于点 产生的某个 ，查看其它点产生的 中 的最小值，然后将 贡献到答案即可。

（查询除去自己后的最小值，只需记录最小值和次小值）

若 不是正确的 ，则会将 算大，不会影响答案。

暴力存储空间复杂度达到了 ，可能导致 MLE。

于是对每个 分别处理，即将 限制在 的子树内，然后在 的点分树上找祖先。

这样，空间复杂度就降为 甚至 。

不难发现，若扩展到 棵树的情况，也能做到 时间， 空间。