给定一棵无根树，假设它有n个节点，节点编号从1到n, 求1-n这n个节点，到其他n-1个节点的距离之和。

输入
第一行包含一个正整数n (n <= 100000)，表示节点个数。
后面(n - 1)行，每行两个整数表示树的边。
输出
每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。
输入样例
4
1 2
3 2
4 2
输出样例
5
3
5
5

裸的换根。

我们先一次dfs处理出每个节点到子树的距离之和。然后再一次dfs做下换根，方程也很简单，不难推出。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,d[N],s[N],sz[N],res[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void dfs1(int x,int fa){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs1(to[i],x); sz[x]+=sz[to[i]]; d[x]+=d[to[i]]+sz[to[i]];
	}
}
void dfs2(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		res[to[i]]=d[to[i]]+(res[x]-d[to[i]]-sz[to[i]])+n-sz[to[i]];
		dfs2(to[i],x);
	}
}
signed main(){
	cin>>n;
	for(int i=1,x,y;i<n;i++)	
		scanf("%lld %lld",&x,&y),add(x,y),add(y,x);
	dfs1(1,1); res[1]=d[1];	dfs2(1,1);
	for(int i=1;i<=n;i++)	printf("%lld\n",res[i]);
	return 0;
}