60分求助
查看原帖
60分求助
496340
Cangshu楼主2021/10/26 11:04
#include <bits/stdc++.h>
using namespace std;
#define maxn 110
struct node {
	int left, right, father;
}t[maxn];

int n, u, v, dis, vis[1005];  //dis记录距离, vis保证每个节点只访问一次
queue <int> q, s;

void cal (int x, int n) {   //从u节点开始遍历整个树,父亲距离就+2,左右子树+1,找到了v就记录一下
	if (vis[x] != 0 || !x) return;
	if (x == v) {
		dis = n;
		return;
	}
	vis[x] = 1;
	cal(t[x].father, n + 2);
	cal(t[x].left, n + 1);
	cal (t[x].right, n + 1);
}

int main () {
	int last = 0, tmp, width = 1, heigh = 0;//宽度最小为1
	cin >> n;
	n--;
	while (n--) {
		cin >> tmp;
		if (tmp != last) {
			last = tmp;
			cin >> t[last].left;
			t[t[last].left].father = last;
		}
		else {
			cin >> t[last].right;
			t[t[last].right].father = last;
		}
	}
	cin >> u >> v;
	t[1].father = 1;
	q.push(1);
	while (!q.empty() || !s.empty()) { //bfs记录高度和宽度,q就是正常bfs的栈,s用来记录每一层的宽度
		node now = t[q.front()];
		if (now.left) s.push(now.left);
		if (now.right) s.push(now.right);
		q.pop();
		if (q.empty()) {
			int t = s.size();
			width = max (width, t);
			heigh++;
			while (!s.empty()) {
				q.push(s.front());
				s.pop();
			}
		}
	}
	cal(u, 0);
	cout << heigh << endl << width << endl << dis;
	return 0;
}
2021/10/26 11:04
加载中...