专栏文章

p3525 sol（POI2011 INS）

AAllenJYL
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqqeytn
此快照首次捕获于
2025/12/04 09:03
3 个月前
此快照最后确认于
2025/12/04 09:03
3 个月前
查看原文
根据题意，设点 ii 为根，考虑其答案。发现如果其存在一棵子树大小大于 n2\frac{n}{2} 就不合法，否则就合法。
记 d=∑dis(i,x)d=\sum\mathrm{dis}(i,x)。
对于合法的点，讨论其是否存在一棵子树 TT 大小等于 n2\frac{n}{2}，
  • 若存在，则答案为 2d−max⁡x∈T(dis(i,x))2d-\max_{x\in T}(\mathrm{dis}(i,x))；
  • 否则答案为 2d−max⁡(dis(i,x))2d-\max(\mathrm{dis}(i,x))。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...