每周三场模拟赛，用来记录。
2023.11.22
计数场。
\(100+0+0+0=100\)。
- C0392 B 【1109 B组】预处理器
题意：求有多少个长度为 \(n\) 的数组 \(a\) 满足以下条件。
-
条件一：\(l_{i} \le a_{i} \le r_{i}\)。
-
条件二：\(a_{i}\) 模 \(2\) 等于 \(p_{i}\)。
-
条件三：\(s \le \sum a_{i} \le t\)。
求答案模 \(mod\) 的值，\(mod\) 不一定是一个质数。
数据范围：\(n \le 13\)。
又积累到一个新的 Trick：看到这种 \(2^{n}\) 能过的数据范围，又是计数，可以往容斥方面想。
显然，\(a_{i}=2\times x_{i}+p_{i}\)，那么将构造数组 \(a\) 转化为构造数组 \(x\)，这样可以消除条件二。
发现可以把条件三转化为 \(a_{i} \le t\) 的答案减去 \(a_{i} \le s-1\) 的答案，这样更好统计答案。然后考虑转化条件一，把上界 \(r_{i}\) 去掉，做容斥即可。具体来讲，设 \(S\) 为一个 \(n\) 位的二进制串，如果第 \(i\) 为 \(1\)，就需要满足 \(a_{i} \ge r_{i}+1\)，为 \(0\) 则需要满足 \(a_{i} \ge l_{i}\)。最后的答案就是 \(S\) 中 \(1\) 的数量为偶数时的答案减去 \(S\) 中 \(1\) 的数量为奇数时的答案（容斥）。
那对于每一个 \(S\)，怎么计算答案呢？首先可以将 \(a_{i}\) 的和的上界 \(tot\) 减去每一个 \(a_{i}\) 的下界，因为每一个 \(a_{i}\) 都至少有这么多。然后问题就转化成了有 \(n\) 个相同盒子和 \(tot\) 个相同球，每个盒子可以放任意个球（可以为零），有多少种本质不同的放法，显然插板法直接做即可。
注意：\(mod\) 不是质数，没有逆元，所以在算组合数的时候要先把分母算出来，然后和分子一一约分，最后将分子相乘即可。
2023.11.24
\(100+40+55+0=195\)。
- C0396 【1124 C组】模拟测试 ksum
题意：你有一个长度为 \(n\) 的正整数数组，第 \(i\) 个数为 \(a_{i}\)。你求出了这个数组的所有子段和，并将这些数降序排序，请输出前 \(k\) 个数。
首先预处理出 \(a\) 数组为前缀和，\(b\) 数组为后缀和的逆序，将题意转化为求 \(a_{i}+b_{j}\) 的前 \(k\) 小。
做法一 (赛时做法)：首先枚举 \(a\) 数组，对于每一个 \(a_{i}\)，以及范围在 \(1\) 到 \(k/i\) 中的所有 \(j\) ，把 \(a_{i}+b_{j}\) 放入优先队列，输出前 \(k\) 个即可。为什么只需要枚举范围在 \(1\) 到 \(k/i\) 中的所有 \(j\)？因为 \(a\) 数组中的 \(1\) 到 \(n\) 和 \(b\) 数组的 \(1\) 到 \(k/i\) 已经组成了 \(k\) 个数了，后面的数肯定比它们小，时间复杂度 \(O(n \log^{2} n)\)。
做法二：维护一个优先队列存当前 \(a_{i}+b_{j}\) 的最小值，然后将它计入答案，并且将 \(a_{i+1}+b_{j}\) 和 \(a_{i}+b_{j+1}\) 加入队列，因为 \(i\) 和 \(j\) 前面的数一定已经计入答案了，而后面最小的一定是 \(a_{i+1}+b_{j}\) 和 \(a_{i}+b_{j+1}\)。时间复杂度 \(O(n \log n)\)。
- C0396 【1124 C组】模拟测试 label
题意：有一棵含有 \(n\) 个节点的树，你现在要给每个节点赋一个 \(1\) 到 \(m\) 之间的整数权值，并保证有边直接相连的两个节点的权值之差的绝对值大于等于 \(k\)，你想知道有多少种不同的赋值方案，两个方案不同当且仅当个点中至少有一个点的权值被赋值的不同，输出答案对 \(1e9+7\) 取模后的值。
首先设 \(dp_{i,j}\) 表示点 \(i\) 的值为 \(j\) 时 \(i\) 的子树中的总方案数，则答案为 \(\sum_{i=1}^{m} dp_{1,i}\)。
那么 dp 转移方程为 \(dp_{u,i}=\sum_{j=i-k}^{i+k} dp_{v,j}\)，但是这是 \(O(nm)\) 的，只有 \(40\) 分。
我们可以发现，其实每一个 \(u\) 的 \(m\) 个 dp 值的中间很长一段都是相同的，准确来说，应该只有前后的 \((n-1)k\) 个值是不同的 (每往上转移一次两边会多 \(k\) 个值不同，一共最多 \(n-1\) 条边)，于是我们可以把中间这一段相同的值特殊记录一下，然后前后的 \((n-1)k\) 个不同的 dp 值直接暴力转移即可，时间复杂度 \(O(n^{2}k)\)。
- C0396 【1124 C组】模拟测试 最短路
题意：有一个 \(n\) 个点 \(m\) 条边的无向图，给定图中的 \(k\) 个点，求一条经过这 \(k\) 个点的路径，保证这条路径是某两个点之间的最短路，并且让长度尽量小，数据保证有解。
很巧妙。
因为要求路径必须是一条最短路并且长度最小，所以不妨直接让两个端点在这 \(k\) 个点中，这样一定更优。然后又因为这条路径是两个点的最短路，所以一定是一次性穿过这 \(k\) 个点的一条链。又因为数据保证有解，于是我们可以用类似于找树的直径的方法，先随便拎 \(k\) 的点中的任意一个点出来，跑到这 \(k\) 个点中离它最远的点 \(u\)，在从这个点 \(u\) 开始跑到离 \(u\) 最远的点，这个距离就是答案。
- C0396 【1124 C组】模拟测试 square
题意：给定一个 \(n\times m\) 的地图 \(a\)，\(a_{i}\) 为 \(0\) 或 \(1\)。有 \(t\) 次询问，每次询问给定一个矩形，求出这个矩形中最大的由 \(1\) 构成的正方形的边长是多少。
首先考虑预处理出 \(d_{i,j}\) 表示以 \((i,j)\) 为左上角的最大正方形边长是多少。
对于每一次询问可以二分一个 \(mid\)，判断 \(mid\) 是否可行就相当于是查询 \(d\) 的一个二维区间中的最大值，如果这个最大值大于等于 \(mid\) 说明可行，否则不可行，注意如果这个二维区间的长宽的最小值比 \(mid\) 小的话，那么肯定不可行。而二维区间 \(\max\) 直接用二维 ST 表维护即可，时间复杂度 \(O(n^{2} \log ^{2}n+t \log n)\)。
2023.11.27
\(100+0+0+10=110\)。
- C0398 【1127 B组】模拟测试 路径
题意：给定一棵 \(n\) 个点的树，对于每一个 \(k=0\) 到 \(n\)，求出满足 \(mex(S(u,v))=k\) 的数量，其中 \(mex(S(u,v))\) 表示 \(u \to v\) 的路径的点的编号的 \(mex\) 值。
很简单。当 \(mex=k\) 时当且仅当 \(0\) 到 \(k-1\) 编号的点都出现过，但是编号为 \(k\) 的点没有出现。容斥一下即可，转化为求有多少条路径满足：经过了编号为 \(1\) 到 \(k\) 中的所有点。
我们只需要从小到大枚举 \(k\)，对于当前枚举到的 \(i\)，分类讨论一下然后把它加入路径即可，时间复杂度 \(O(n\log n)\)。
- C0398 【1127 B组】模拟测试 序列
题意：给定一个长度为 \(n\) 的序列，求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。你还可以将其中 \(k(k \le 20)\) 个数修改为任意的值。
一个小 Trick：如果两个数乘起来为平方数，可以先将每个数的平方因子除掉，然后这两个数必然相等。于是这道题被转化为了一个区间不能有相等的值。
首先考虑没有修改的情况怎么做，设 \(pos_{a_{i}}\) 表示上一个 \(a_{i}\) 出现在哪里（也就是最远可以满足条件的位置），那么有 dp 转移方程 \(dp_{i}=dp_{pos_{a_{i}}}+1\)，时间复杂度 \(O(n)\)。
然后考虑有修改操作的情况，我们可以稍微改变一下 \(pos\) 数组的定义，改为 \(pos_{i,j}\) 表示当前点为 \(i\)，修改 \(j\) 次后可以到达的最远的满足条件的位置。那么怎么转移呢？\(pos_{i,j}=\min(pos_{i-1,j-1},last+1)\)，\(last\) 表示上一个 \(a_{i}\) 出现的位置。因为 \(pos_{i-1,j-1}\) 和 \(last+1\) 这两个位置都有可能是修改次数的分界点，看哪个更小即可。然后就可以用 \(pos\) 数组来 dp 转移了：\(dp_{i,j}=dp_{pos_{i,k},j-k}+1\)。最终的答案就是 \(dp_{n,k}\)，时间复杂度 \(O(nk^{2})\)。
注意分解质因数的时候可以先将质数线性筛出来，这样效率更高。
- C0398 【1127 B组】模拟测试 游戏
题意：有一个 \(n\) 个点的环，以及两个人。每个人可以向环中任意一个位置放置一个 \(A\) 或者 \(B\)，但是相邻的位置不能相同，不能行动者输。问最终的局面有多少种。
一个结论是：后手必胜。
证明：最终肯定不可能出现两个连续的空格，否则一定可以在其中一个上填 \(A\) 或 \(B\)。所以最多只有一个空格，而这个空格两边填的字母一定是不一样的，否则一定可以在这填一个和它两边不一样的字母。所以如果把所有空格去掉之后，一定是 \(ABABAB\dots\)(\(k\) 个 \(AB\)) 的形式。步数一定为偶数，所以后手必胜。
问题转化成了有多少种在环上放空格的方式，使得每两个空格都不相邻。可以先断环为链，然后分类讨论，假设当前要选 \(i\) 个空格(必须满足 \(n-i\) 为偶数)。如果链的第一个位置为空格，则后面 \(n-1\) 个要选出 \(i-1\) 个空格且首尾不能选，方案数 \(C^{i-1}_{n-i-1}\)(插空法)；如果链的第一个位置不为空格，则后面 \(n-1\) 个要选出 \(i\) 个空格且首尾可以选，方案数 \(C^{i}_{n-i}\)(插空法)。注意还要乘以 \(2\times(n-i)!\)，\(2\) 表示可以从 \(A\) 开始也可以从 \(B\) 开始，\((n-i)!\) 表示每个人每次选择位置的顺序。
枚举 \(i\)，累计答案即可。
2023.11.29
\(0+40+40+0=80\)。
- C0400 【1129 B组】模拟测试 算面积
题意：有一个 \(n\times m(n,m \le 10^{5})\) 的图，每个点都是一个 \(0\) 到 \(9\) 的数字，但每一行的数都是循环的，循环节为 \(a_{i}(a_{i} \le 100)\)。另外有 \(t\) 个询问，每个询问给出一个矩形，求这个矩形内数的和。(时限 \(4s\))
赛时写出来了，但是因为数组开大 MLE 了。直接二维前缀和时空都是 \(O(nm)\) 的。但是因为循环节很小，所以可以对于每一种循环节做二维前缀和。询问时对于每一种循环节计算答案，先把中间重复的一大段直接加上，然后用预处理出来的 \(sum\) 数组求值即可。时间复杂度 \(O(100\times t\log n)\)，常数大，空间复杂度 \(O(100n)\)。如果把询问离线下来，可以做到 \(O(n \times 100^{2})\)，常数小。
- C0400 【1129 B组】模拟测试 猜数
题意：给定一个数 \(z\)，求有多少个 \(x\) 满足 \(x+f(x)=z\)，其中 \(f(x)\) 表示将 \(x\) 翻转。
奇奇妙妙构造题。
将 \(z\) 存到 \(b\) 数组（\(n\) 为最高位，\(1\) 为最低位）中，可以发现，如果不进位的话，那么 \(z\) 的每一位一定是左右对称的（\(b_{i}=b_{n-i+1}\)）。考虑如何求出不进位情况下的 \(b\) 数组。依次从外到内处理 \(z\) 的每一位，假设当前处理到的位置为 \(l\)，右边对应的位置为 \(r\)。如果 \(b_{l}=b_{r}\) 则已经合法，直接跳过即可；如果 \(b_{l}>b_{r}\)，因为 \(r+1\) 到 \(n\) 已经确定了，所以 \(b_{r}\) 不可能增加了，只能变 \(b_{l}\)。我们可以将 \(b_{l}\) 减去 \(10\)，然后将 \(b_{l+1}\) 加一，这样总的值是不会变的（相当于是借了一位）；如果 \(b_{l}<b_{r}\) 的话，不可能让 \(b_{l}\) 直接加 \(10\)，因为这样一定会大。所以我们可以让 \(r\) 这一位是最终 \(r-1\) 这一位进位得到的。所以 \(b_{r}\) 减 \(1\)，\(b_{r-1}\) 加 \(10\)。又因为 \(r-1\) 这一位最终要进位，对称过去 \(l+1\) 也要进位，所以 \(b_{l+1}\) 加 \(10\)，\(b_{l+2}\) 减一。
这样就求出 \(b\) 数组了，最终只需要计算总方案数即可。一开始 \(res=1\)，如果 \(b_{i}=x_{1}+y_{1}=x_2+y_2=x_3+y_3=\dots=x_k+y_k(0\le x_i,y_i\le 9)\)，那么就将 \(res\) 乘上 \(k\) 即可。
注意最开始如果 \(z\) 的最高位为一且最低位为一的话既有可能是两个比 \(z\) 少一位的数加起来也有可能是两个和 \(z\) 位数相同的数加起来。如果最高位为一但是最低位不为一就只有可能是两个比 \(z\) 少一位的数加起来（否则最低位一定为一），如果最高最低为都不为一那么只能是两个和 \(z\) 位数相同的数加起来。
- C0400 【1129 B组】模拟测试 排序
题意：有一个 \(n\) 个数的序列 \(a\)，我们从 \(1\) 到 \(n\) 排序。如果当前排到 \(i\) 号且它不是它后面的所有数的最小值，那么花费 \(1\) 的代价将它放到最后。求结束排序时花费的代价。
我们会发现每一次不会被排到最后的数一定是当前还没有被排序的数中的最大值。所以我们可以从大到小统计每一种数的代价。把一直往后面放数的操作转化成一个指针在环上面移动，且只会走过没有被排序的数，指针移动的步数就是相应的代价。那么对于每一个数 \(i\)，指针会移动多少呢?指针的起始位置一定是上次 \(i-1\) 的结束位置，并且这个指针会经过每一个值为 \(i\) 的位置，并且在最后一个值为 \(i\) 的位置停下，这个距离是很好算的。但是中途不会经过已经排好序的数，即大于 \(i\) 的数，还需要减去这一部分的代价，用树状数组维护即可，时间复杂度 \(O(n \log n)\)。
2023.12.1
\(90+25+20+5 = 140\)。
- C0402 【1201 B组】模拟测试 串
题意：构造一个长度为 \(n\) 且包含 \(k\) 个 \(1\) 的 \(01\) 串，使得包含奇数个 \(1\) 的区间个数最多。
赛时打表找规律做的，发现前 \(k-1\) 个 \(1\) 全部在左边，剩下的一个 \(1\) 放在剩下所有位置的中间。但是没有特判 \(k=0\) 的情况挂了 \(10\) 分。
讲一下证明。首先算出这个串的前缀异或和数组 \(a\)，假设区间 \(l\) 到 \(r\) 有奇数个 \(1\)，那么一定有 \(a_{r}+a_{l}=1\)。所以如果 \(a_{0}\) 到 \(a_n\) 一共有 \(x\) 个 \(1\)，\((n+x-1)\) 个 \(0\)，那么满足条件的区间数为 \(x(n+x-1)\)。用均值不等式求最大值即可。发现构造方法和上述一样。
- C0402 【1201 B组】模拟测试 黑白树
题意：给定一棵 \(n\) 个点的树，每一个结点都可以是黑色或白色。定义一棵树的价值，为同色点距离的最大值。求出在所有情况下，树的价值之和，对 \(10^9 + 7\) 取模.
很显然，同色点的最大距离一定是树的直径。令直径的两个端点为 \(x,y\)，我们从大到小考虑每个距离对应多少种情况，假设答案距离为 \(i\)，那么所有到 \(x\) 距离 \(> i\) 的点颜色必须与 \(y\) 一样，所有到 \(y\) 距离 \(> i\) 的点颜色必须和 \(x\) 一样。假设当前的总情况数为 \(tot\)，那我们可以利用容斥的原理，假设不满足上述条件（最大距离 \(\le i -1\)）的情况数为 \(k\)，那么满足条件的情况数就为 \(tot-k\)。那么问题在于如何求 \(k\)，其实只要距离 \(x,y\) 的距离等于 \(i\) 的所有点都刚好分别为两个颜色的时候，其它点无论怎么取值，情况都一定不合法，因为最大距离一定小于 \(i\)，所以只需要预处理出 \(2^{p}\) 即可。然后每一次要将 \(tot\) 赋值为 \(k\)，因为 \(k\) 就是当最远距离为 \(i - 1\) 时的总情况数。 时间复杂度 \(O(n)\)。
2023.12.5
\(90+30+0+0=120\)。
- C0429 【1205 B组】模拟测试 猫咪
题意：有 \(n(n \le 10^9)\) 个点，每次可以选择在当前点停下或者向右跳 \(1/2/k(k \le 10^2)\) 个点。初始时可以跳到任何一个点上。求经过的点组成的序列的种数。
场切了，但是细节没处理好挂了 \(10\) 分。感觉对矩阵优化 dp 的理解深刻了不少。
设 \(dp_{i}\) 表示在 \(i\) 以及 \(i\) 之前的点停下的方案数。那么有一个类似于前缀和的转移：
\(dp_i=dp_{i-1}+(dp_{i-1}+(dp_{i-1}-dp_{i-3})+(dp_{i-k}-dp_{i-k-1}))\)。
朴素转移是 \(O(n)\) 的，用矩阵可以优化到 \(O(k^3 \log n)\)。
- C0429 【1205 B组】模拟测试 字符串
题意：给出⼀个长度为 \(n\) 的字符串，你需要求这个字符串所有子序列的价值和。一个字符串的价值指这个字符串的所有的长度⼩于等于 \(\left \lceil \frac{n}{2} \right \rceil\) 的 border 的长度的和（\(n \le 300\)）。
看到数据范围，我们可以想到类似于区间 dp 的东西。因为 border 前后完全相同，所以我们设 \(f_{i,j}\) 表示有多少对子序列满足前一段结束于 \(i\)，后一段结束于 \(j\)，且两段相同。 但是我们发现即使求出了 \(f\) 数组我们也只知道有多少对 border 串而不知道具体的长度。所以我们可以多枚举一个 \(p\) 表示后一段开始的位置为 \(p\)，并且设 \(g_{i,j}\) 表示满足条件的子序列的长度之和，这样最终答案就是：\(\sum_i\sum_j g_{i,j} \times 2^{\max(p-i-1,0)}\)。（因为两段中间的位置都可以选或不选）
接下来考虑如何转移，\(f\) 的转移是普通的：\(f_{i,j}=\sum_{k=1}^{i}\sum_{o=i}^{j}f_{k,o}\)。但是如何转移 \(g\)？其实我们会发现，\(g\) 的每一次转移相当于在每一个 border 串的后面再添加了一个字符，所以当前的 \(g\) 就应该等于用来转移的 \(g\) 加上当前有多少 border 串，也就是 \(f\)。于是有：\(g_{i,j}=\sum_{k=1}^{i}\sum_{o=i}^{j}f_{k,o}+g_{k,o}\)。这两个方程朴素转移是 \(O(n^5)\) 的，用二维前缀和可以优化到 \(O(n^3)\)。
注意当 border 的长度等于 \(\left \lceil \frac{n}{2} \right \rceil\) 时要加一，因为它自己一个字符可以作为子序列。
2023.12.7
\(100+100+0+6=206\)。
- C0431 【1207 B组】模拟测试 小数点
题意：计算 \(\frac{n}{m}\) 的小数点后第 \(l\) 到 \(r\) 位。\((n,m,l,r \le 10^9,r-l+1 \le 10^5)\)
先将 \(\frac{n}{m}\) 乘上 \(10^{l-1}\)，然后对于每一位直接暴力除即可，时间复杂度 \(O(r-l+1)\)。
- C0431 【1207 B组】模拟测试 体力劳动
题意：给定一个长度为 \(n(n \le 10^5)\) 的序列 \(a\) 和一个数 \(x\)。求出一个最小的 \(len\)，使得存在一个长度为 \(len\) 的区间满足这个区间进行冒泡排序的交换次数大于 \(x\)。
首先冒泡排序的交换次数其实就等价于区间逆序对数。看到求最小值，考虑二分。对于每一个 \(mid\)，我们可以从左往右维护一个长度为 \(mid\) 区间，如果有一个长度为 \(mid\) 的区间的逆序对数大于 \(x\)，那么 \(mid\) 就是合法长度。现在问题转化成了如何动态维护长度为 \(mid\) 的区间的逆序对数。看到维护逆序对数，容易想到权值树状数组。具体来讲，动态维护一个答案 \(ans\)，区间每一次向右移动，都要将 \(ans\) 减去左端点的贡献，加上右端点的贡献。并且在树状数组上也要做相应的修改。时间复杂度 \(O(n \log^2 n)\)。
- C0431 【1207 B组】模拟测试 距离之和
题意：给出一颗 \(n\) 个点的无根树，对于每一个点 \(u\)，求出最少进行多少次操作才能使得 \(f(u)\) 小于等于任意的 \(f(v)\)。\(f(x)\) 指所有点到 \(x\) 点的距离和，一次操作指删一条边，再任意填一条边，保证原图还是一棵树。
要让 \(f(u)\) 是所有点中最小的，当且仅当 \(u\) 为重心，证明可以用反证。于是问题就变成了对于每一个 \(u\)，问需要操作多少次才能使得 \(u\) 变为重心。我们先找到当前的重心 \(root\)，显然重心的答案为 \(0\)。并且以这个重心为根求出每个点的 \(size\)。
前置知识：\(u\) 的最大子树大小小于等于 \(\frac{n}{2}\) 是 \(u\) 为重心的充分必要条件。
先只考虑删边。对于一个点 \(u\)，考虑删成什么样子的时候才能使得存在一种连边方式使得 \(u\) 为重心。我们会发现满足上述条件当且仅当：删完边后，不包含 \(u\) 的联通块的大小小于等于 \(\frac{n}{2}\)，包含 \(u\) 的联通块中所有子树的大小小于等于 \(\frac{n}{2}\)。所以只需要考虑如何尽可能少地删边，使图满足这个条件即可。
设 \(b_u\) 表示点 \(u\) 的祖先节点中和 \(root\) 相邻的那一个（形象地说就是 \(u\) 所在子树的顶点）。如果我们想要把 \(u\) 变为重心，那么我们会发现：
-
如果删了一条 \(root\) 的其它子树内的边，则将那条边换成那个子树与 \(root\) 相连的边，方案仍然合法。这是因为那个子树之外的点所属连通块不会变大，而那整个子树的大小也不会超过 \(\frac{n}{2}\)。
-
如果删除了 \(b_u\) 子树内部的边，则将那条边换成 \(b_u\) 与 \(root\) 相连的边，方案仍然合法。这是因为 \(b_u\) 子树之外的点所属连通块不会变大，而 \(b_u\) 这颗子树的大小也不会超过 \(\frac{n}{2}\)。
综上，我们先贪心地只删 \(root\) 和某个点之间的边，且贪心地按 \(size\) 从大到小删，只到剩下的联通块的大小 \(\le \frac{n}{2}\) 为止，记录删了多少条边（\(ans\)）即可。
但是最终包含 \(u\) 的那一个联通块的大小不一定小于 \(\frac{n}{2}\)，所以我们还要考虑包含 \(u\) 的那一个联通块的大小大于 \(\frac{n}{2}\) 的情况。
如果是这种情况，那么最终 \(b_u\) 到 \(root\) 的边一定是留下来的（否则不可能大于 \(\frac{n}{2}\)），那么还需要分类讨论。
-
如果 \(b_u\) 到 \(root\) 的边已经被删了，那么我们判断是否可以将这条边连上，是则更新答案。并且可以证明不可能再连其它边了，不然包含 \(u\) 的这个联通块的子树大小就大于 \(\frac{n}{2}\) 了。
-
如果 \(b_u\) 到 \(root\) 的边没有被删，那么我们判断是否可以把原来删过的最小的子树连回去，是则更新答案。并且可以证明不可能再连其它边了，不然包含 \(u\) 的这个联通块的子树大小就大于 \(\frac{n}{2}\) 了。
最后会发现一个神奇的结论，最后的答案一定是 {\(0,ans,ans-1\)} 其中之一，且取到 \(ans-1\) 的情况一定是包含 \(u\) 的那一个联通块的大小大于 \(\frac{n}{2}\) 的情况，时间复杂度 \(O(n)\)。