CSP-S 2026 T4
考场上浏览一遍试卷,刚看到半径惊呼一声集宝
题意
ans=S组成联通块≤2,∣S∣=kmin1≤i≤nmaxj∈Smindis(i,j)
因为
minmax
状物考虑 2 分答案 . (是因为我一开始想的是类似于分割 2 - 带权联通块换根 DP 类 CSP-S 2019 D2T3但发现并没有什么太大的前途, 也许是自己太弱了吧)
设临时答案为 mid 检查可行性,由于直觉告诉我是贪心,于是使用吧.
Part1. 1 个连通块的情况
首先考虑一个大联通块 :
考虑自底向上贪心,首先不用叶子节点,因为对距离没有太大贡献.
于是考虑拆了 mid 轮叶子节点之后的剩余数量 ∣Stemp∣≤k.( 预处理每个点删除直到第 r 轮,然后就可以拆, 即 hi≤mid 时删除 )
Part2. 2 个连通块的情况
然后实在不行再考虑两个大联通块( 前提是 ∣Stemp∣−k≤2mid )
在 Stemp 中删掉一条链, 剩下的两部分分别作为一个连通块.
如何删除呢 ?
首先,叶子不能删,因为删完之后就距离会增加且分不成 2 块,
其次 u∈Stemp,degree(u)≥3 不能删, 删完之后就拆成 ≥3个了不符合,
综上所述只能拆 u∈Stemp,degree(u)=2 了.
也就是所谓的,设可删链总长度为 lenth 要在这一个大联通块里面找到一个首先满足 u∈Stemp,degree(u)=2,lenth≥∣Stemp∣−k 这一条件的一条链.
其次满足 :
链上节点 v1,v2,…vlenth 中删除 [l,r],r−l+1=∣Stemp∣−k.
于是链上节点到 2 个大联通块的最短距离即为 min(i−l+1,r−i+1), 因此还需满足
∀i∈[l,r],hi+min(i−l+1,r−i+1)≤mid
注意此处 hi 是不沿链方向走能到达的最远点距离.
然后你就可以进行拆拆拆了 ( 注意可以删除的是1条链,度数是在 Stemp 内的度数 ).
时间 O(N+NlogN) N=∑n
空间 O(n)
本人是蒟蒻,推导若有错误请指正

有帮助,赞一个