unt

?

20251107

• 上午 T1 正确性：下称连通块大小为该连通块内可用的度数和，初始时显然等于点数的二倍。关键性质，考虑用 \(w\) 最大的边将树分开后，所有达到最大不同块之间连边次数的方案，最后要么所有点都用完了，要么有剩下点的连通块为最大的那个连通块。

  证明：考虑设最大的连通块大小为 \(mx\)，所有连通块大小和为 \(S\)。情况一，如果 \(mx\) 大于其他所有连通块的大小和，那么显然最大方案是让其他所有块向最大块建立连接，建立的连接总数为 \(S-mx\)，如果任意两个非最大块之间有边，那么将消耗 \(S-mx\) 中的 \(2\) 个来建立一对连接，显然不优。情况二，如果 \(mx\) 不大于其他所有连通块的大小和，即 \(mx\le S-mx\)，那么这种情况必然可以将全部可用度数都消耗完，原因是，可以构造一种策略，即每次选择当前最大的两块并连一条边。