本来不想写的。

邮寄

\(100+100+100+35=335\)

在过去一学期里并不短暂地离开了 OI，自以为功力全消，而我所能做的仅仅是重温做题以外的比赛，与比赛以外的做题。万事万物中为数不多能带来些许真实的，只是手指触上键盘的冰凉，钢笔划过稿纸的阻滞。

在学竞赛的这四年里，我的身份在综合与竞赛的来回切换间变得模糊，既不全似文化课选手，也不全似竞赛生。在高中数学物理学得心力交瘁时曾有长辈提过文科的建议，然而纵然我对侍弄笔墨自有十足底气，却到底不信日后能存留皓首穷经的几分热情。

对竞赛则是反过来，我或许有些许热情，但我毫无能力。

考场门口有人踱步皱眉紧张踟蹰，有人谈笑风生热血难凉——这些自然属于那些陌生而年轻的初中面孔。我只能闭目冥思，迷惘着未来，剖白着心境——那些在材与不材之间的一片空白。

整场考试我都无限平静，读题、推敲、编码，这些动作甚至几乎近于机械和麻木。高二终于达到了我初三的目标，多可笑啊。只在我全然不在乎也无所希冀的时候，结果带来些许甜头，而我分辨不清，这该是奖赏还是诱惑。

  • \(\texttt{T1}\) 读错题了，成功让我耗时二十分钟。
  • \(\texttt{T2}\) 题面好长，自认为我像模拟赛那样做不出来的概率不低。读完题十分钟过了。
  • \(\texttt{T3}\) 怎么感觉这么简单？写写画画二十分钟推完细节，不太想写，休息了二十分钟，零零碎碎调了将近一个小时过了。
  • \(\texttt{T4}\) 乱猜一手结论，猜错了，不重要了。

题解

前三题都没什么好说的。

简单提及 T3 考场思路：最短路径唯一时，一定进行极长的跳跃。观察到合法点对有且仅有连续两步跳跃存在两种情况，枚举这两步跳跃起点所处的位置，可以根据起点找到一段终点区间。起点与终点前后可能各自衔接一段唯一最短的路径（具体能否衔接需要分类讨论），以某点起始或结束的唯一最短路径数量可以简单地通过线性 dp 解决。

P17834 [CSP-S 2026] 研发基地 / hub

评价我考场以直径作为突破口的尝试：在某一程度上，对于针对某一科目的考试这种高度 task-specific 的训练，形成思维定式是训练有素的表现，但形成错误的思维定式并不是。

二分答案 \(R\)，剥离原树外层的 \(R\) 轮叶子，考虑余树 \(C_r\)，最终所选点一定在 \(C_r\) 中。

排除两种简单的情况：若 \(|C_r|\leq k\)，则可以直接全选；若 \(|C_r|> 2R\)，则一定无解。

令 \(res=|C_r|-k\)，表示余树 \(C_r\) 中需要钦定至少 \(res\) 个节点不被选择。则考察必须被选择的节点类型：

  • 余树 \(C_r\) 的叶节点必被选择，否则原树中最外层叶子到被选点集合的距离将大于 \(R\)。
  • 度数大于 \(2\) 的节点必被选择，否则被选择的叶节点将被划分到大于 \(2\) 个连通块中。

由此可以找出若干条 \(C_r\) 上有度数为 \(2\) 的点组成的极长链，我们所希望的就是在其中某一条链上找出长度为 \(res\) 的可删区间。此时对链的区间内的点是否可以删除产生限制的只有链的每个点的原树子树内最远叶子到区间两端点的距离。

遍历链的每个节点，可以使用差分标记标记出由这个点原树下挂的叶子节点所禁止的链上可删区间的起点位置连续段，最后统计是否存在不被标记的起点位置即可。

// Time Limit : 3.0 s
// Memory Limig :1024 MiB
/* --------------- Code Below ---------------  */#include 
using namespace std;typedef long long i64;
#define I inline
#define reg register
typedef pair pint;
#define fi first
#define se second
#define mk make_pairchar BG;namespace Input {char ibuf[(1<<21)+1], *p1 = ibuf, *p2 = ibuf;#define gh() (((p1==p2)&&(p2=(p1=ibuf)+fread(ibuf,1,1<<21,stdin)),p1==p2)?EOF:*p1++)template T read() {T x = 0, sgn = 1;reg char c = gh();while (!isdigit(c)) (c=='-')&&(sgn=-1), c = gh();while (isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = gh();return x*sgn;}
}
using namespace Input;constexpr int N = 2e6+5;int cid, T, n, K;
int a[N], b[N], d[N], to[N], deg[N];int tim[N], que[N], head, tail;
void toposort() {head = 1, tail = 0;for (int i = 1; i <= n; i++)if (deg[i] == 1) que[++tail] = i, tim[i] = 1;while (head <= tail) {int u = que[head++];for (int _ = d[u]; _ < d[u+1]; _++) {int v = to[_];if (--deg[v] == 1) que[++tail] = v, tim[v] = tim[u]+1;}}
}int vis[N], key[N];vector find(int lst, int cur) {vector rst;while (deg[cur] == 2 && !vis[cur]) {vis[cur] = true;int nxt = 0, dep = 0;for (int _ = d[cur]; _ < d[cur+1]; _++) {int x = to[_];if (!key[x]) dep = max(dep, tim[x]);else if (x != lst) nxt = x;}rst.emplace_back(dep);lst = cur, cur = nxt;}return rst;
}bool check(int radius) {int res = accumulate(tim+1, tim+n+1, 0, [&](int x, int y) { return x+(y>radius); })-K;if (res <= 0) return true;if (res > 2*radius) return false;for (int i = 1; i <= n; i++) key[i] = tim[i] > radius;for (int i = 1; i <= n; i++) vis[i] = false;for (int u = 1; u <= n; u++) {deg[u] = 0;if (!key[u]) continue;for (int _ = d[u]; _ < d[u+1]; _++) {int v = to[_];deg[u] += key[v];}}for (int u = 1; u <= n; u++) {if (!deg[u] || deg[u] == 2 || vis[u]) continue;for (int _ = d[u]; _ < d[u+1]; _++) {int v = to[_];if (deg[v] != 2 || vis[v]) continue;vector limits = find(u, v);if ((int)limits.size() < res) continue;int m = (int)limits.size()-res+1;vector tag(m+1, 0);for (int i = 0; i < (int)limits.size(); i++) {int len = radius-limits[i];int l = max(i+len-res+1, 0), r = min(m-1, i-len);if (l <= r) ++tag[l], --tag[r+1];}for (int i = 0; i < m; i++) {if (i) tag[i] += tag[i-1];if (tag[i] == 0) return true;}}}return false;
}void solve() {n = read(), K = read();for (int i = 1; i <= n+1; i++) d[i] = 0;for (int i = 1; i < n; i++) {a[i] = read(), b[i] = read();++d[a[i]], ++d[b[i]];}for (int i = 1; i <= n; i++) deg[i] = d[i];for (int i = 1; i <= n; i++) d[i+1] += d[i];for (int i = 1; i < n; i++) {to[--d[a[i]]] = b[i];to[--d[b[i]]] = a[i];}toposort();int L = 0, R = *max_element(tim+1, tim+n+1);while (L < R) {int mid = (L+R)>>1;if (check(mid)) R = mid;else L = mid+1;}printf("%d\n", L);
}char ED;#define filename "hub"
int main() {
#ifdef filenamefreopen(filename".in", "r", stdin);freopen(filename".out", "w", stdout);
#endiffprintf(stderr, "[Static Memory : %.3lf MiB]\n", abs(&BG-&ED)/1024.0/1024.0);clock_t st = clock();cid = read(), T = read();while (T--) solve();clock_t ed = clock();fprintf(stderr, "[Time : %.3lf s]\n", (ed-st)/1000.0);return 0;
}