题目描述

一棵树有 $n$ 个结点，结点编号为 $1$~$n$，其中 $1$ 号结点为根结点，根结点的深度为 $1$，请问每个结点的父结点是谁，每个结点的深度是多少。

输入格式

第一行是整数 $n$，表示结点数。（$1 \le n \le 100$）

后面若干行，每行两个整数 $a , b$，读入数据不保证结点 $a$ 是结点 $b$ 的父结点。

本题测试数据保证所有结点能构建为一棵树。

输出格式

输出有 $n−1$ 行（根结点不需要输出），每行输出 $3$ 个整数；

第 $i$ 行输出：结点编号 $i+1$，编号为 $i+1$ 的结点的父结点的编号，该结点的深度（三个整数之间用空格隔开）。

样例

5
2 1
4 3
1 3
3 5

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

解题思路

做这一题的前提，是你已经搞定了树的高度.1， 1 和 2 的区别是：树的高度.1明确父子关系中谁是父亲，谁是儿子。而树的高度.1故意不透露，只知道父子关系，但是不提供谁是父，谁是子。

幸好，根节点是提供的，我们只需要从根节点往下找就可以了。

我们把和 a 有父子关系的节点都统统当做 a 的儿子，放入 a 的儿子链表（可以用动态数组实现）。所以，这个写子节点里，有 1 个是错的，因为那个是 a 的父亲。所以，在 dfs 的时候，需要加以区分。dfs 函数增加一个参数，就是 a 节点的父亲。在枚举 a 的儿子的时候，判断一下是不是 a 的父亲，如果是，那就跳过。

用一个 bool 数组来对访问过的节点上锁也行，但是如果是程序填空题，很可能是考上面的这个方法，所以一定要会。

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,k,ans;
int h[101],fa[101]; // h 用来记录深度， fa 用来记录父亲是谁 
vector <int> child[101];
void dfs(int p, int father) // p 的父节点是 father 
{
	for(int i=0;i<int(child[p].size());i++){
		if( 填空(1) ) // 如果 是 p 的父亲，就不需要递归了，否则死循环的 
		{ 
			h[ 填空(2) ] = h[p]+1;
			fa[ 填空(2) ] = 填空(3);
			填空(4);
		}
	}
}
int main()
{
	scanf("%d",&n);

	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		// 这里不区分 a 和 b 谁是父亲谁是儿子。把 a 加到 b 的儿子数组里，也吧 b 加到 a 的儿子数组里。递归的时候再来区分 
		child[b].push_back(a); 
		child[a].push_back(b); 
	}

	h[1] = 1;
	填空(5);

	for(int i=2;i<=n;i++)
		printf("%d %d %d\n",i,填空(6),填空(7));

	return 0;
}

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

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

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

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

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

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

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