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