题目描述

给定一棵树的边的关系，结点 $1$ 为该树的根，请问该树的宽度（同一层最多的结点数）、高度（根结点的高度为 1 ），以及树中两个结点 $u$ 和 $v$ 之间的最短距离是多少？

比如：下图所示的树，深度为 $5$，宽度为 $3$，结点 $7$ 到结点 $9$ 的最短距离为 $5$。

输入

第 $1$ 行输入一个整数 $n$（$n \le 1000$）；

接下来 $n−1$ 行，每行有 $2$ 个整数 $x$ 和 $y$，表示结点 $x$ 和 $y$ 之间有一条边（$1 \le x,y \le n$）。

最后一行有 $2$ 个整数 $u$ 和 $v$ ，表示求 $u$ 和 $v$ 之间最短距离。

输出

第 $1$ 行输出该树的高度；

第 $2$ 行输出该树的宽度；

第 $3$ 行输出该树从结点 $u$ 到结点 $v$ 之间最短距离；

样例

10
2 1
1 3
2 4
5 2
3 6
7 4
8 5
9 8
10 8
7 9

5
3
5

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,depth[1001],heigh[1001],father[1001];
vector <int> e[1001];
map <int, int> w;
void create_tree(int u,int fa){
	father[u] = __填空(1)__;
	depth[u] = __填空(2)__; // 该子节点的深度等于它的父亲的深度 + 1
	w[depth[u]]++; //顶点 u 的深度为 depth[u]， 记录每一个深度的顶点数量
	
	for(auto it=e[u].begin();it!=e[u].end();it++) {// 链表的遍历
		int v = *it;
		if(__填空(3)__) {
			create_tree(__填空(4)__);
			heigh[u] = max(heigh[u],heigh[v]);
		}
	}

    heigh[u]++;
}

int get_lca(int u, int v){
	//先保证 u 和 v 深度一致
	if(depth[u]<depth[v]) __填空(5)__;
	while(__填空(6)__) u = father[u];

	//同一深度的比较
	while(u!=v){
		u = father[u];
		__填空(7)__;
	}

	return __填空(8)__;
}

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

	create_tree(__填空(9)__);
	cout<<heigh[1]<<endl;

	int width=0;
	for(auto it=w.begin();it!=w.end();it++){
		width = max(width,it->second);
	}
	cout<<width<<endl;

	int u,v;
	cin>>u>>v;
	int lca = get_lca(u,v);

	cout<<depth[u] + __填空(10)__;

	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) }}