题目描述

现在有一棵 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~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

算法知识

本题我们要学习一下前向星算法存储边的信息。如果是自己写程序，可以用动态数组来绕过这个问题，但是，考试填空题经常考到这个算法，所以我们不进要会 STL vector，还要会前向星。

前向星是一种基于链表来存储 树、图数据结构中的边信息的方法。每一个节点都有一条链，所以每一个节点都有一个链头（代码中的 h 数组）。因为整条链都是从这个节点出发的，所以，边不需要存放起点信息，只需要存放终点（代码中的 To 成员变量）即可。

下面，我们用一张图来展现题目中的这棵树基于前向星算法的存放办法。

要定义一个存放边信息的结构体：

struct Edge
{
	int to,next;
}e[200];

结构体有两个成员，to 是用来存放这条边的终点；next 是用来存放链表的下一个节点的 id (id 就是数组下标)

然后，每一个节点都有一条属于自己的 边链，通过 h 数组来存放每条链的链条。

题目说的边并不明确父子关系，所以，这些边都是无向边。输入数据的每一条无向边，在 e 数组里要表达成 2 条有向边。

上面这个数据，用链表的思维导图来表现，就是下面这个样子。当链条到了最后一个节点的时，next 成员为空。

上面这个结构，能够很容易找到一个节点的所有的边，跟邻接表相比，这个数据结构很节省存储空间。

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,sz[105],depth[105],tot,h[105]; // h 是链表的头，每个节点一个链头
struct Edge{
	int to,next;
}e[200];
// e 数组 用来记录第 j 条表连接那个节点，它是链表结构。表链里的元素从属于某个节点，所以这条边的源点不需要单独记录
// 100 个节点，会有99*2=198 条边，如果实际的边比这个数字多，那就是构成环路了，
// tot 是用来记录当前用到第几条边。

void add(int u,int v){ // 增加一条从顶点 u 到顶点 v 的边
	// 采用链表的“头部插入法”
	e[++tot] = {__填空(1)__};  // tot 是 e 数组的下标，每增加一条边，tot 就递增 1
	h[u] = __填空(2)__;
}

void dfs(int u,int father){
	sz[u]=1; //即便没有儿子，也有自己，最少的 size 是 1
	depth[u] = __填空(3)__; // 该子节点的深度等于它的父亲的深度 + 1
	for(int i=__填空(4)__;__填空(5)__;__填空(6)__) {// 链表的遍历
		int v = e[i].to;
		if(__填空(7)__) {
			dfs(__填空(8)__);
			sz[u] += __填空(9)__;
		}
	}
}

int main(){
	scanf("%d",&n);
	int x,y;
	for(int i=2;i<=n;i++){
		scanf("%d%d",&x,&y);

		// 增加一条从 x 到 y 的有向边
		add(x,y);

		// 增加一条从 y 到 x 的有向边
		add(y,x);
	}

	dfs(__填空(10)__);

	for(int i=1;i<=n;i++)
		printf("%d %d\n",sz[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) }}

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

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