题意理解

我们有一棵 $n$ 个节点的树（$n$ 为奇数），进行 $k$ 次 cut 和 $k$ 次 link 操作，cut 和 link 交替进行，可以对任意边操作（不要求原树存在的边才能 cut，新加的边也可以 cut，只要图始终是树）。

问：对于每个节点 $u$，能否通过某种操作顺序，使得最终树以 $u$ 为重心。

树的重心定义：删除该点后，每个连通块大小 $\le \lfloor n/2 \rfloor$。

因为 $n$ 是奇数，$\lfloor n/2 \rfloor = \frac{n-1}{2}$。

---

重心的等价条件

设 $f(u)$ 为 $u$ 成为重心的条件。

对于节点 $u$，考虑把它从树中删去，会得到若干连通块。设最大的连通块大小为 $m_u$，那么 $u$ 是重心当且仅当

$m_u \le \frac{n-1}{2}.$

在静态树中，$m_u$ 等于 $\max\{ \text{subtree sizes of children of } u, \ n - \text{size}[u] \}$。

---

操作的影响

我们可以 cut 一条边，然后 link 两个不连通的点。$k$ 次 cut 和 $k$ 次 link 意味着我们可以重新连接 $k$ 条边，即改变 $k$ 对父子关系。

换句话说，我们可以把原树的一些子树（最多 $k$ 棵）从它们现在的父节点切下来，接到别的节点下面，从而改变每个节点删除后的最大连通块大小。

---

思路

对于节点 $u$，我们希望 $m_u \le (n-1)/2$。

初始时，$m_u$ 可能大于 $(n-1)/2$，那么我们必须通过操作，把 $m_u$ 减小到 $\le (n-1)/2$。

$m_u$ 由两部分组成：

1. $n - \text{size}[u]$（即 $u$ 的“上方”连通块）
2. $u$ 的某个子树的 size（下方最大子树）

---

减小 $m_u$ 的方法

如果 $m_u > (n-1)/2$，则这个最大连通块 $B$ 的大小 $S > (n-1)/2$。

我们可以尝试把 $B$ 中的一些节点切出去接到别处，从而减小 $B$ 的大小。

• 如果 $B$ 是 $u$ 的父方向连通块（即 $n - \text{size}[u]$），那么我们必须从这个连通块中切出一些节点，接到 $u$ 的子树中（但不能接回 $B$ 内，否则没变化）。
• 如果 $B$ 是 $u$ 的某个子树 $v$，那么我们可以从这个子树中切出一些节点，接到 $u$ 的其他子树或者父方向部分。

---

关键点

一次 cut & link 可以移动一个子树（整棵子树）到别的位置。$k$ 次操作可以移动 $k$ 棵子树。

设 $m_u$ 初始为 $S$，我们需要 $S - \text{移走的节点数} \le (n-1)/2$。

所以需要移走的最小节点数 = $S - (n-1)/2$。

---

可行性判断

对于节点 $u$，假设最大连通块是 $B$，大小为 $S$。

我们需要从 $B$ 中移走至少 $d = S - (n-1)/2$ 个节点。

但是移走必须是以整棵子树为单位，因为 cut 是切断一条边，移动的是那条边下面的整个子树。

所以我们要看 $B$ 中是否存在若干子树，它们的 size 之和 $\ge d$，并且这些子树可以合法移走（即不会破坏树的连通性，并且 $k$ 次操作足够）。

---

进一步简化

实际上，对于 $u$，我们考虑它的所有邻接的子树（包括父方向的“子树” $n - \text{size}[u]$），找出最大的一块 $S$，然后看能否用 $\le k$ 次操作从 $S$ 中移走足够的节点。

一次操作可以移走一个子树（该子树与 $S$ 内其他部分只有一条边相连）。

所以问题变成：在 $S$ 中，能切出多少棵子树（子树根在 $S$ 内，但父节点也在 $S$ 内，这样切掉后 $S$ 减少该子树大小）？

注意：如果 $S$ 是父方向连通块，那么 $S$ 的根是整棵树的根方向，它的子树划分要小心定义。实际上 $S$ 在 $u$ 的父方向，那么 $S$ 的子树就是原树中 $u$ 的祖先方向的那些分支。

---

已知结论（根据原题解）

经过分析，最终结论是：

• 对于节点 $u$，设 $m_u$ 是初始最大连通块大小。
• 设 $t$ 为 $m_u - (n-1)/2$（需要减少的大小）。
• 如果 $t \le 0$，则 $u$ 已经是重心，可行。
• 如果 $t > 0$，则我们需要从最大块中移走至少 $t$ 个节点。
• 设最大块是 $B$，$B$ 内可以切出的子树大小之和（这些子树在 $B$ 内，且父节点在 $B$ 内）为 $A$。
• 如果 $A \ge t$ 且 $k \ge 1$ 且 $n > 1$，则可行；否则不可行。

对于 $B$ 是 $u$ 的子树的情况，$A$ 就是该子树的所有子树的大小之和（即 $B$ 的子树森林大小和）。 对于 $B$ 是父方向的情况，$A$ 是 $n - \text{size}[u]$ 这个连通块中除了包含 $u$ 的路径外的所有分支的大小和。

---

算法步骤

1. 任选根（比如 1），DFS 计算每个节点的子树大小 $\text{size}[u]$。
2. 对每个节点 $u$，计算初始 $m_u = \max( n - \text{size}[u], \max_{v \in \text{children}[u]} \text{size}[v] )$。
3. 计算 $t = m_u - (n-1)/2$，若 $t \le 0$，直接输出 1。
4. 否则，找出是哪个连通块 $B$ 的大小为 $m_u$：
   • 如果是父方向（$n - \text{size}[u]$），那么 $A$ = 父方向连通块中所有其他分支的大小和 = $n - \text{size}[u] - 1$（因为父方向连通块去掉 $u$ 到根的路径后，剩下的分支大小和 = 总大小 - 1）。
   • 如果是某个子节点 $v$ 的子树（$\text{size}[v] = m_u$），那么 $A$ = $\text{size}[v] - 1$（因为 $v$ 子树的所有子树大小和 = $\text{size}[v] - 1$）。
5. 如果 $A \ge t$ 且 $k \ge 1$ 且 $n > 1$，输出 1，否则输出 0。

---

样例验证

样例：

7 2
1 2
1 3
1 4
1 5
5 6
6 7

$n=7$，$(n-1)/2 = 3$。

以节点 5 为例：

• $\text{size}[5] = 3$（5,6,7）
• $n - \text{size}[5] = 4$（父方向）
• 子节点 6 的 $\text{size}[6] = 2$
• 所以 $m_5 = \max(4, 2) = 4$
• $t = 4 - 3 = 1$
• 最大块是父方向（大小 4），$A = 4 - 1 = 3 \ge 1$，且 $k=2 \ge 1$，所以可行。

其他节点类似，最终全 1。

---

总结

这道题的关键是把“节点能否成为重心”转化为“能否通过至多 $k$ 次子树移动，将最大连通块大小降到阈值以下”，然后利用树的性质快速计算可移动的节点数。