P15654

rehtam · 2026-03-09 09:49:45 · 题解

考场口胡做法，发现有误请提醒作者。

发现 dist 大的一定优于小的，两棵树排名相同当且仅当同构。于是比较子树内点等价于比较儿子，据此可以得到平方做法。

由于 dist 是第一关键字，考虑以直径中心为根，那么 x 到根 链上的点 一定是最优的几个点。

以上是考场写了的。

考虑点对点的情况，等价于减去一条链中比一个点优的，可以随便来个 ds 维护。

以上是考场没写完的。

考虑链对链，剩下两种情况与其相似。等价于对一条链上的每个点减去 另一条带有权值的链中 比它优的。权值可以拆成以 1 为权值和以深度为权值。作者并未仔细想这个能否 polylog，但是可以用 top cluster 树分块做到单根号。