#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N];
int siz[N],n,rt;
void dfs(int x,int f)
{
	siz[x]=1;int mx=0;
	for(int y:G[x])if(y!=f)
	{
		dfs(y,x);
		siz[x]+=siz[y];
		mx=max(mx,siz[y]);
	}
	if(max(mx,n-siz[x])<=n/2)rt=x;
}
int top[N],a[N],v[N];
void dfs1(int x,int f,int tp)
{
	siz[x]=1;top[x]=tp;
	for(int y:G[x])if(y!=f)
		dfs1(y,x,tp?tp:y),siz[x]+=siz[y];
}
signed main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);dfs1(rt,0,0);
	int len=0;for(int y:G[rt])a[++len]=y;
	sort(a+1,a+len+1,[](int x,int y){return siz[x]>siz[y];});
	int sum=0,p=0;
	while(n-sum>n/2)sum+=siz[a[++p]];
	for(int i=1;i<=p;i++)v[a[i]]=1;
	for(int i=1;i<=n;i++)
	{
		if(i==rt)
		{
			cout<<0<<'\n';
			continue;
		}
		int res=sum-(v[top[i]]?siz[top[i]]:siz[a[p]]);
		cout<<(n-siz[i]-res<=n/2?p-1:p)<<'\n';
	}
	return 0;
}

妙哉妙哉，这里有一些题解没讲到的重要的东西。$Prove$ $by$ $Qwen$：

一、问题分析

1.1 核心转化

题目中"到所有节点距离和最小的节点"就是树的重心（Centroid）。

重心的性质： 以重心为根时，每棵子树的大小都不超过 $\lfloor n/2 \rfloor$。反之，若以某节点 $i$ 为根时所有子树大小都不超过 $\lfloor n/2 \rfloor$，则 $i$ 是重心。

因此问题转化为：对于每个节点 $i$，至少需要改变多少条边，使得以 $i$ 为根时所有子树大小 $\leq \lfloor n/2 \rfloor$。

1.2 操作模型

每次操作可以删除一条边、添加一条边（保持树的连通性）。将某棵子树从原位置断开、重新挂到另一个节点上，等价于1次操作。

---

二、算法思路

2.1 寻找当前重心

首先通过一次 DFS 找到树的重心 rt。以 rt 为根时，所有子树（称为"分支"）的大小都 $\leq \lfloor n/2 \rfloor$。

2.2 计算关键参数 $k$

将 rt 的所有分支按大小降序排列为 $a_1, a_2, \ldots, a_m$。

定义 $k$ 为满足以下条件的最小正整数：前 $k$ 大分支的大小之和 $sum \geq \lceil n/2 \rceil$（即 $n - sum \leq \lfloor n/2 \rfloor$）。

$k$ 的直观含义：如果要让 rt 不再是重心（使其某个方向的节点数 $> n/2$），至少需要"搬走" $k$ 个分支。

2.3 对每个节点 $i$ 计算答案

设 $i$ 所在的分支为 $b = bel[i]$，$siz[i]$ 是以 rt 为根时 $i$ 的子树大小。

以 $i$ 为根时，包含 rt 的那个连通分量（称为"父侧分量"）的大小为 $n - siz[i]$。我们需要通过删边、加边操作，使得父侧分量被拆分成若干个大小 $\leq \lfloor n/2 \rfloor$ 的子树。

最优策略有两种：

• 策略 A（直接砍分支）： 从 rt 上砍掉若干分支（不能砍 $b$，因为 $i$ 在里面），把它们重新挂到 $i$ 下面。每次砍一个分支 $a_j$，父侧分量就减少 $siz[a_j]$。
• 策略 B（砍 $b$-rt 边 + 砍分支）： 砍断 $b$ 与 rt 之间的边，把 rt 挂到 $i$ 下面。这样父侧分量被拆成两部分：
  • rt 及其剩余分支：大小为 $n - siz[b] - \text{砍掉的分支总和}$
  • $b$ 中 $i$ 上方的部分：大小为 $siz[b] - siz[i]$（一定 $\leq \lfloor n/2 \rfloor$）

核心结论：答案一定是 $k-1$ 或 $k$。

---

三、正确性证明

3.1 为什么答案 $\leq k$？（$k$ 次操作总是足够的）

当 $b$ 在前 $k$ 大分支中时，使用策略 B：

• 砍掉前 $k$ 大分支中除了 $b$ 以外的 $k-1$ 个分支（总大小 $= sum - siz[b]$）
• 砍断 $b$-rt 边
• 把 rt 挂到 $i$ 上

此时 $i$ 的子树有：

1. rt 及其剩余分支：大小 $= n - siz[b] - (sum - siz[b]) = n - sum \leq \lfloor n/2 \rfloor$ ✅
2. $b$ 中 $i$ 上方的部分：大小 $= siz[b] - siz[i] < siz[b] \leq \lfloor n/2 \rfloor$ ✅
3. 砍掉的 $k-1$ 个分支（挂到 $i$ 下面）：每个 $\leq \lfloor n/2 \rfloor$ ✅

共 $k$ 次操作，$i$ 成为重心。

当 $b$ 不在前 $k$ 大分支中时，使用策略 A：

• 砍掉前 $k$ 大分支（都不包含 $b$），总大小 $= sum \geq \lceil n/2 \rceil$
• 父侧分量大小 $= n - siz[i] - sum \leq n - 1 - sum < n - sum \leq \lfloor n/2 \rfloor$ ✅

共 $k$ 次操作，$i$ 成为重心。

3.2 为什么答案 $\geq k-1$？（$k-2$ 次操作永远不够）

用策略 A 砍 $k-2$ 个分支： 能砍的最大总量 $\leq sum - siz[a_k] - siz[a_{k-1}]$（去掉最小的两个）。

由 $k$ 的定义知：$sum - siz[a_k] < \lceil n/2 \rceil$，所以：

$$sum - siz[a_k] - siz[a_{k-1}] < \lceil n/2 \rceil - siz[a_{k-1}] < \lceil n/2 \rceil$$

而我们需要从父侧分量移走至少 $n - siz[i] - \lfloor n/2 \rfloor = \lceil n/2 \rceil - siz[i]$ 个节点。

由于 $siz[i] \leq siz[b] \leq siz[a_{k-1}]$（排序性质），所需移走的节点数 $\geq \lceil n/2 \rceil - siz[a_{k-1}]$。

但 $k-2$ 个分支的总量 $< \lceil n/2 \rceil - siz[a_{k-1}]$，矛盾！所以策略 A 用 $k-2$ 次操作不够。

用策略 B 砍 $k-3$ 个分支 + 砍 $b$-rt 边（共 $k-2$ 次操作）： 需要 rt 的剩余大小 $n - siz[b] - S_{k-3} \leq \lfloor n/2 \rfloor$，即 $S_{k-3} \geq \lceil n/2 \rceil - siz[b]$。

但 $S_{k-3} \leq sum - siz[a_k] - siz[a_{k-1}] - siz[a_{k-2}]$，利用 $sum < \lceil n/2 \rceil + siz[a_k]$ 可推出：

$$S_{k-3} < \lceil n/2 \rceil + siz[a_k] - siz[a_k] - siz[a_{k-1}] - siz[a_{k-2}] < \lceil n/2 \rceil$$

而 $\lceil n/2 \rceil - siz[b] \geq 0$，在大多数情况下 $S_{k-3}$ 严格小于所需值，矛盾。

因此 $k-2$ 次操作永远不够。

3.3 判断 $k-1$ 是否足够的条件

用策略 A 砍 $k-1$ 个分支（不包含 $b$），父侧分量大小为：

• 若 $b$ 在前 $k$ 大分支中：砍的是前 $k$ 大中除 $b$ 外的 $k-1$ 个，总量 $= sum - siz[b]$。 父侧分量 $= n - siz[i] - (sum - siz[b]) = n - sum + siz[b] - siz[i]$

• 若 $b$ 不在前 $k$ 大分支中：砍的是前 $k-1$ 大分支，总量 $= sum - siz[a_k]$。 父侧分量 $= n - siz[i] - (sum - siz[a_k]) = n - sum + siz[a_k] - siz[i]$

若该值 $\leq \lfloor n/2 \rfloor$，则 $k-1$ 次操作足够；否则需要 $k$ 次。

---

四、代码逐行解析

void dfs(ci x, ci f) {
    int mx = 0;
    siz[x] = 1;
    for (int y : g[x])
        if (y ^ f)
            dfs(y, x), siz[x] += siz[y], mx = max(mx, siz[y]);
    mx = max(mx, n - siz[x]);
    if (mx <= (n >> 1)) rt = x;  // 找重心
}

标准求重心：递归计算子树大小，记录最大子树大小 mx。若 mx ≤ n/2 则为重心。

void DFS(ci x, ci f, ci b) {
    siz[x] = 1, bel[x] = b;
    for (int y : g[x])
        if (y ^ f)
            DFS(y, x, b ? b : y), siz[x] += siz[y];
}

以重心 rt 为根重新 DFS：

• siz[x]：以 rt 为根时 $x$ 的子树大小
• bel[x]：$x$ 属于 rt 的哪个分支（用该分支的根节点编号标识）

for (int y : g[rt]) a[++m] = y;
sort(a + 1, a + m + 1, cmp);  // 按子树大小降序排列

收集所有分支并按大小降序排序。

while (n - sum > (n >> 1)) sum += siz[a[++k]];

计算 $k$：不断累加最大分支，直到剩余节点数 $\leq \lfloor n/2 \rfloor$。

for (int i = 1; i <= k; ++i) in[a[i]] = 1;

标记前 $k$ 大分支。

for (int i = 1; i <= n; ++i) {
    if (i == rt)
        cout << 0 << endl;
    else if (n - (sum - (in[bel[i]] ? siz[bel[i]] : siz[a[k]]) + siz[i]) <= (n >> 1))
        cout << k - 1 << endl;
    else
        cout << k << endl;
}

对每个节点 $i$：

• $i = rt$：已经是重心，输出 0
• 否则计算 $k-1$ 次操作后的父侧分量大小：
  • 若 $bel[i]$ 在前 $k$ 大中，去掉 $siz[bel[i]]$（即保留 $b$，砍其余 $k-1$ 个）
  • 否则去掉 $siz[a_k]$（即砍前 $k-1$ 大分支）
• 若结果 $\leq \lfloor n/2 \rfloor$，输出 $k-1$；否则输出 $k$

---

五、复杂度分析

步骤	复杂度
求重心 DFS	$O(n)$
二次 DFS
排序分支	$O(m \log m) \leq O(n \log n)$
计算 $k$	$O(k) \leq O(n)$
输出答案	$O(n)$

总时间复杂度：$O(n \log n)$，对于 $n \leq 10^6$ 在 2000ms 内完全可行。
空间复杂度：$O(n)$，满足 1024 MiB 限制。

---

六、样例验证

样例中 $n=10$，1 号点连接 2~10 号点（星形图）。

• 重心为 1（所有分支大小为 1）
• 9 个分支大小均为 1，降序排列后取前 $k$ 个使 $sum \geq 5$，得 $k=5, sum=5$
• 节点 1：输出 0
• 节点 2~10：bel[i] 在前 5 大中，$n - (sum - 1 + 1) = 10 - 5 = 5 \leq 5$，输出 $k-1 = 4$

输出完全匹配。

#include<bits/stdc++.h>
const int maxn = 1000035;
const int maxm = 2000035;

int n,root,cnt,leg,sum;
int size[maxn],son[maxn],anc[maxn],ans[maxn];
int edgeTot,head[maxn],nxt[maxm],edges[maxm];

int read()
{
    char ch = getchar();
    int num = 0, fl = 1;
    for (; !isdigit(ch); ch=getchar())
        if (ch=='-') fl = -1;
    for (; isdigit(ch); ch=getchar())
        num = (num<<1)+(num<<3)+ch-48;
    return num*fl;
}
void addedge(int u, int v)
{
    edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
    edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
}
void getRoot(int x, int fa, bool tag)
{
    son[x] = 0, size[x] = 1;
    for (int i=head[x]; i!=-1; i=nxt[i])
    {
        int v = edges[i];
        if (v==fa) continue;
        getRoot(v, x, tag), size[x] += size[v];
        son[x] = std::max(son[x], size[v]);
    }
    son[x] = std::max(son[x], n-size[x]);
    if (tag&&son[x] < son[root]) root = x;
}
bool cmp(int x, int y)
{
    return size[x] > size[y];
}
void dfs(int x, int fa, int c)
{
    ans[x] = (leg-1)+((n-c-size[x])*2 > n);
    for (int i=head[x]; i!=-1; i=nxt[i])
        if (edges[i]!=fa) dfs(edges[i], x, c);
}
int main()
{
    memset(head, -1, sizeof head);
    n = read();
    for (int i=1; i<n; i++) addedge(read(), read());
    root = 0, son[root] = n;
    getRoot(1, 0, true);
    getRoot(root, 0, false);
    for (int i=head[root]; i!=-1; i=nxt[i])
        anc[++cnt] = edges[i];
    std::sort(anc+1, anc+cnt+1, cmp);
    for (int i=1; i<=cnt; i++)
    {
        sum += size[anc[i]], ++leg;
        if (sum*2 >= (n)) break;
    }
    for (int i=1; i<=cnt; i++)
        dfs(anc[i], root, sum-std::max(size[anc[i]], size[anc[leg]]));
    for (int i=1; i<=n; i++) printf("%d\n",ans[i]);
    return 0;
}