博客

现在有一棵n个节点的树，节点1为这棵树的根，求出每个节点的深度以及每个节点的子树中的节点个数。

输入

第1行：一个数字n，表示树中节点的个数。(1<=n<=100000)

第2-n行：每行两个数字u,v，表示u与v之间有一条边。(1<=u,v<=n)

输出

输出n行，每行两个正整数，第i行的第一个正整数表示节点i的深度，第二个正整数表示以节点i为根的子树大小。

输入样例

10

1 2

1 3

1 4

2 5

2 8

4 6

4 7

6 9

6 10

输出样例

1 2 2 2 3 3 3 3 4 4

10 3 1 5 1 3 1 1 1 1

和

2281 树的Size之和（并查集）

差不多，修改一下就行

#include<bits/stdc++.h>
using namespace std;
int fa[1010],num[1010],layer[1010];
int x,y;
void find(int x)
{
 num[x]++;
 layer[y]++;
 if(fa[x]!=x)
  find(fa[x]);	
}
int main()
{
 ios::sync_with_stdio(false);
 int n,sum=0;
 cin>>n;
 for(int i=1;i<=n;i++)
  fa[i]=i;
 for(int i=1;i<n;i++)
 {
 	cin>>x>>y;
 	find(x);
 	fa[y]=x;
 }
 for(int i=1;i<=n;i++)
  cout<<layer[i]+1<<" ";
 cout<<endl;
 for(int i=1;i<=n;i++)
  cout<<num[i]+1<<" ";
 return 0;
}