原题

【问题描述】

我仿佛忆起了自己的故乡，因为这些回忆的色彩总是有点朦胧。但我也许只是想到了些其他东西。

这也许不是我那实实在在的故乡，也许是别人的故乡，也许只是我内心的臆想。

但我越过记忆里的水洼，水洼边的城镇，学校，寺庙，我终于到达了故乡的背面。

那里只有一棵老树。

这棵老树是一棵极其特殊的树。

它有n个节点，节点之间是光滑的树枝连接的，树枝一共有n-1条。因为这是一棵树，所以每一对节点之间都是可以通过树枝直接或者间接到达的。

我们给这些节点从1到n标号，一号节点就是根。对于每一根树枝链接的两个节点，我们称到1号节点距离更远的那个节点是另一个节点的孩子（因为孩子节点是从另一个上面长出来 的）。

我们称从一个节点直接或者间接长出来的所有节点（包括其本身）组成了以这个节点为根的子树。

我们发现每一个节点都在漫长的时间里与一些在他子树内的节点产生了共鸣（我们称这些点对于这个节点是“好点”）。经过长时间的观察，我们发现能跟节点i产生共鸣的好点，一定是以i为根的子树中，到这棵子树里所有点的最短距离之和最小的那些点（可能不止一个）。

KeineDuck路过了这一颗树，他想知道对于每个节点，都有哪些节点是“好点”。

因为他沉迷线段树无法自拔，所以这个问题就交给你了。

【输入格式】

输入文件名为 extree.in。

第一行一个正整数n，表示树的节点个数。

接下来n-1行，每行两个正整数u,v，表示存在一条连接u号节点和v号节点的树枝。

【输出格式】

输出文件名为 extree.out。

输出n行，第i行若干个数，表示所有对于节点i的好点。请你把这些点按照编号大小升序输出

题面（简化）

给出一棵树（$n$ 个节点），现要求 $\forall i\in[1,n]$，输出以 $i$ 节点为根的子树的所有重心的编号。

$n≤1000000$，若一棵子树有多个重心，按字典序输出，小的在前，大的在后。

题解

考虑一个比较显然的性质：

把两棵树通过一条边相连得到一棵新的树，那么 新树的重心在连接原来两棵树的重心的路径上。

那么我们在 dfs 合并子树的时候，从两棵子树的重心开始往它的祖先跳（因此我们要预处理出 fa 数组，这也很简单，一遍 dfs 即可），直到跳到合并后的重心为止。

如何判断跳到的这个点是不是合并后的重心？利用重心的另一个性质即可：

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

我们只需要预处理出 size 数组（表示以它为根的子树中的节点个数），然后如下判断:（$pre[i]$ 表示以 $i$ 为根的子树的重心位置）

若 size[x]-size[pre[x]]≤size[x]/2 成立，则 $pre[x]$ 是以 $x$ 为根的子树的重心。

由于精度问题，最好将右边的除以 $2$ 移到左边变成乘 $2$。如果你想化简这个式子，那当然也是可以的（但我没有）。

好了，那就剩下最后一个问题了：在这么一通操作之后，我们也只求出了一个重心。如果一棵子树有多个重心，那又应该怎么处理呢？

其实非常简单，因为重心还有另外几个性质：

1：一棵树的重心最多只有两个

2：若一棵树有两个重心，那么这两个重心一定直接连接。

3：若一个节点的是这棵树的重心，它的一个子节点也是这棵树的重心，那么这个子节点一定是它的 最重子节点

这几个性质都非常显然（但其实都是 wbx 告诉我的）。有了它们之后就好办了，我们可以直接在输出的时候找到它的父节点与最重子节点（都可以预处理出来），判一下就好。

至于怎么判，其实有很多种方法，在这里我选择使用和刚才一样的方法。我们预处理出一个 $w$ 数组，表示这个节点的子树中节点个数最多的那棵子树的节点数，然后把刚刚那个式子稍微改一下就行（具体见代码）。

此外就是输出的细节问题了，这玩意把我卡了两个小时。一定要注意先输出小的，再输出大的！我们需要先把答案存一下判断大小，再输出。

完整代码

题解中的 $pre$ 数组就是代码中的 $son$ 数组。$wson$ 数组存的就是每个节点的最重子节点。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*w;
}
const int N=4e6+5;
struct node{
    int next,to;
}e[N];
int head[N],num,n,siz[N],fa[N],son[N],w[N],wson[N];
void add(int from,int to)//好不容易用一次链式前向星存图
{
    e[++num].next=head[from];
    e[num].to=to;
    head[from]=num;
}
void dfs(int fr)
{
    son[fr]=fr,siz[fr]=1;
    for(int i=head[fr];i;i=e[i].next)
    {
        int ca=e[i].to;
        if(ca==fa[fr]) continue;
        dfs(ca);
        siz[fr]+=siz[ca];
        w[fr]=max(w[fr],siz[ca]);
        if(siz[ca]>siz[wson[fr]]) wson[fr]=ca;
    }
    for(int i=head[fr];i;i=e[i].next)
    {
        int ca=e[i].to;
        if(ca==fa[fr]) continue;
        if((siz[ca]<<1)>siz[fr]) son[fr]=son[ca];
    }
    while((siz[fr]-siz[son[fr]])*2>siz[fr]) son[fr]=fa[son[fr]];
}
void dfs1(int x,int p)
{
	fa[x]=p;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(y!=p) dfs1(y,x);
	}
}
signed main()
{
    n=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
    dfs1(1,0);dfs(1);
    for(int i=1;i<=n;i++)
    {
        int ans1=0,ans2=0;
        son[i]=ans1;
        if(max(w[fa[son[i]]],siz[i]-siz[fa[son[i]]])*2<=siz[i]) son2=fa[son[i]];//可以注意一下这两行判断
        if(max(w[wson[son[i]]],siz[i]-siz[wson[son[i]]])*2<=siz[i]) son2=wson[son[i]];
        if(ans2) printf("%d %d\n",min(ans1,ans2),max(ans1,ans2));
        else printf("%d\n",ans1);
    }
}