不知道什么原因几乎全RE,求调
查看原帖
不知道什么原因几乎全RE,求调
1338385
ffr25楼主2024/8/16 12:00
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
  
  int n, wed = 0, maxn = 1;//wed存储最大宽度,maxn存储最大深度
struct node {
	int le = 0;           //左孩子
	int ri = 0;
	int fa = 0;           //父节点
	int cen = 1;            //结点所在层数
}al[200];             

int search_fa(int p,int q) {        //寻找p,q共同父节点
	if (p == q)return p;
	if (p == 1 || q == 1)return 1;   //找到根结点直接返回
	(al[p].cen <= al[q].cen) ? search_fa(p, al[q].fa) : search_fa(al[p].fa, q);//哪个层数更深就先找哪个的父
}

int main() {
	cin >> n;
	int tem1, tem2 = 0, p, q;
	for (int i = 1; i < n; i++) {
		cin >> tem1;
		if (al[tem1].le)cin >> al[tem1].ri;   //先加默认左孩子
		else cin >> al[tem1].le;
		al[al[tem1].le].cen = al[al[tem1].ri].cen = al[tem1].cen + 1;
		al[al[tem1].le].fa = al[al[tem1].ri].fa = tem1;
		maxn = max(maxn, al[tem1].cen + 1); //非叶子结点的最大层数+1
	}
	tem1 = 1;          //当前搜索层数
	for (int i = 1; i <= n; i++) {
		if (al[i].cen == tem1)tem2++;     //当前层数结点数
		else {
			tem1++;
			wed = max(wed, tem2);
			tem2 = 1;              //重设为1
		}
	}
	wed = max(wed, tem2);  //tem2为最后一层节点数
	cin >> p >> q;
	int fa = search_fa(p, q);     //共同父节点
	cout << maxn << endl << wed << endl;
	int lon = (al[p].cen - al[fa].cen) * 2 + al[q].cen - al[fa].cen;//距离
	cout << lon << endl;
	return 0;
}
2024/8/16 12:00
加载中...