暴力WA#1,蒟蒻求助
查看原帖
暴力WA#1,蒟蒻求助
1004026
__Charlie_Chen__楼主2023/12/10 20:19

c++代码及注释如下:

#include<bits/stdc++.h>//懒人专用万能头无需解释
using namespace std;
struct node {
	int dep, l, r, fa;//dep代表深度,l左孩子,r右孩子
	bool d = false;
} tree[1000];
int sum[100];//记录每层节点数量
int lca(int x, int y) {//lca暴力
	while (x != y)
		if (tree[x].dep > tree[y].dep) x = tree[x].fa;
		else y = tree[y].fa;
	return x;
}
int main() {
	int n;
	scanf("%d", &n);
	tree[1].dep = 1, tree[1].fa = 0;//根节点没有爸爸,深度为1
	int x, y, maxd = 0;
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		if (tree[x].l == 0) tree[x].l = y;
		else tree[x].r = y;
		sum[tree[i].dep]++;//当前节点所在层数数量++
		tree[y].fa = x;//y的爸爸为x
		tree[y].dep = tree[x].dep + 1;
		if (tree[y].dep > maxd) maxd = tree[y].dep;
	}
	int s, t;
	scanf("%d%d", &s, &t);
	int f = lca(s, t), num1 = 0;
	while (s != f) {
		s = tree[s].fa;
		num1+=2;
	}
	while (t != f) {
		t = tree[t].fa;
		num1++;
	}
	int maxx = -1;//求节点数最多的层数
	for (int i = 1; i <= 100; i++) if (sum[i] > maxx) maxx = sum[i];
	printf("%d\n%d\n%d\n", maxd, maxx, num1);
	return 0;
}
2023/12/10 20:19
加载中...