p3525 sol（POI2011 INS）

AllenJYL · 2024-12-19 21:32:25 · 题解

根据题意，设点 i 为根，考虑其答案。发现如果其存在一棵子树大小大于 \frac{n}{2} 就不合法，否则就合法。

记 d=\sum\mathrm{dis}(i,x)。

对于合法的点，讨论其是否存在一棵子树 T 大小等于 \frac{n}{2}，

• 若存在，则答案为 2d-\max_{x\in T}(\mathrm{dis}(i,x))；
• 否则答案为 2d-\max(\mathrm{dis}(i,x))。