题目描述

现在有一棵 n 个结点的树，结点 1 为这棵树的根，结点 1 的深度为 1，求出每棵子树的大小及每个结点的深度。

比如，有如下图所示的树：

该树中：

结点 1 对应的子树大小为 6，深度为 1。

结点 2 对应的子树大小为 5，深度为 2。

结点 3 对应的子树大小为 1，深度为 3。

结点 4 对应的子树大小为 1，深度为 3。

结点 5 对应的子树大小为 2，深度为 3。

结点 6 对应的子树大小为 1，深度为 4。

输入格式

有 $n$ 行。

第 $1$ 行有一个整数 $n$，代表结点的数量，结点的编号为 $1 \sim n$ ( $1 \le n \le 100$ )

接下来有 $n−1$ 行，每行有 $2$ 个整数 $x,y$，表示结点 $x$ 和 $y$ 之间有一条边。（不保证 $x$ 是 $y$ 的父）

输出格式

有 $n$ 行。

第 $i$ 行输出 $2$ 个整数，分别是以编号 $i$ 为根的子树的大小，以及编号 $i$ 对应的结点的深度。

样例

6
1 2
5 2
2 3
4 2
5 6

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

题目分析

顾名思义，本题的数据背景是一棵树。题目是通过给出了树上所有的边来描述这棵树的。边可分成有向边和无向边，本题的边是无向边。但是，无向边可以转换成两条有向边，例如，顶点 2 和 顶点 3 之间有一条无向边，可以理解成有两条有向边，第一条是从顶点 2 出发，到顶点 3；另一条有向边是从顶点 3 出发，到顶点 2 。

本题要我们输出每一个顶点对应的子树的大小，以及顶点的深度。所以，子树的概念和深度的概念需要厘清。一棵树可以拆分成棵子树。讲子树的时候，整棵树的顶点先要确定，本题说 1 号顶点是根。确定了根之后，整棵树就有了方向性，我们说子树就是从某个个顶点出发往叶子方向走，它的儿子，它的儿子的儿子,.....一直到叶子部分。如果不确定整棵树的根，是没办法确定子树的。

第二个是深度，深度和高度是一对相反的概念。深度是指一个顶点距离根节点的距离。往往根节点的深度为 1 （有时候，也会说根结点深度为 0 的，要看题目），我们把树上的节点看成一层一层，这个深度就是从根开始数的第几层。而高度则相反，是指一个顶点距离深度最深的后代有几层。往往叶子节点算是高度为 1 。因此，深度是从根往下数第几层，而高度则是叶子往上数第几层，方向相反，概念类似。

本题的关键就是要从树根出发，遍历整棵树，遍历的过程就可以计算每个节点的子树大小以及深度了。

1. 节点的子树大小 = 该节点所有儿子子树的大小之和 + 1 （儿子子树的大小往往是在儿子的信息计算好之后才有的，所以这个信息刷新操作往往是在 dfs 返回的时候做）
2. 节点的深度 = 父节点的深度 + 1 (dfs 进入某个节点的时候，父节点的深度已经算好，所以可以在 dfs 到儿子节点之前计算好本节点的深度)
3. 节点的高度 = 子节点的高度 + 1 （子节点的高度总是在儿子的信息算好之后有的，所以一般是从递归返回的时候计算节点的高度）
4. 在遍历树节点的时候，可以基于 DFS 算法，但是需要注意避免死循环。因为题目给的数据是没有告诉你这条边的方向的，我们建了 2 条方向相反的有向边，我们要避免从儿子又 DFS 到父亲。所以，在 DFS 的时候，要把父亲信息传进 DFS 函数，我们要在从这个顶点出发的边连排除掉那条指向父亲节点的边。

伪代码

dfs(当前节点 u，父节点 fa){
    depth[u] = depth[fa] + 1; // dfs 到下一层之前执行
    size[u] = 1 ; // 即便没有儿子，子树也有自己，最起码有 1 个节点
    heigh[u] = 1 ;
    for v : 所有的儿子{
		if (v==fa) continue; //这条边是指向父亲的，不能 dfs ，否则会死循环
        dfs(u,v);
        size[u] += size[v];
        heigh[u] = max(heigh[u],heigh[v]+1);
    }
}

最后一个技术关键点，就是如何存放边的信息。一个比较简单的方法，是我们按源点来分别存放这些边，例如，有 3 条边：2->3, 2->4 , 2->5 ，这 3 条边都是从 2 号顶点出发的，我们就存放到一个 vector 里面，每一个顶点都有属于自己的的一些边（就是从自己出发的往别的顶点走的边），所以，我们用一个数组存放

vector <int> e[101]; // 每个数组元素是一个 vector， e[i] 存放这从 顶点 i 出发的边

int x,y;
for(int i=1;i<n;i++){
    cin>>x>>y;
    // x 和 y 之间的无向边，可以理解成 2 条有向边
    e[x].push_back(y); // 从 x 到 y 的有向边，从 x 出发，所以这条边属于 e[x]
    e[y].push_back(x); // 从 y 到 x 的有向边，从 y 出发，所以这条边属于 e[y]
}

完成程序

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1001;
int n;

vector <int> e[maxn];

int depth[maxn],Size[maxn]; // 如果用了万能头文件，size 就不能用了，可以用 Size

void create_tree(int u,int fa){
	depth[u] = __填空(1)__;
	Size[u] = __填空(2)__;
	for(auto it=__填空(3)__;it!=__填空(4)__;it++){
		int v = *it;
		if(__填空(5)__){ //建树的过程是一直往叶子节点方向 dfs 的过程，要避免走错方向死循环
			create_tree(__填空(6)__);
			Size[u] += __填空(7)__;
		}
	}
}
// create_tree() 实际上是 dfs 算法的一个应用

int main()
{
	scanf("%d",&n);

	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}

	create_tree(__填空(8)__);

	for(int i=1;i<=n;i++)
		printf("%d %d\n",Size[i],depth[i]);

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}