社区讨论

82分求助!

P3884[JLOI2009] 二叉树问题参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m1iu6l4e
此快照首次捕获于
2024/09/26 13:11
去年
此快照最后确认于
2024/09/26 18:13
去年
查看原帖
CPP
#include <bits/stdc++.h>
#define clear memset(f, 0, sizeof(f));
using namespace std;

const int N = 105;
int n, x, y, sd, kd, cnt[N];
bool f[N], f_up, f_down;
struct node{
	int father = -1, lson = -1, rson = -1;
} a[N];
void dfs(int x, int sum)
{
	if (a[x].lson != -1 && !f[a[x].lson])
	{
//		cout << sum << endl;
		f[a[x].lson] = 1;
		cnt[sum+1]++;
		sd = max(sd, sum + 1);
		dfs(a[x].lson, sum + 1);
	}
	if (a[x].rson != -1 && !f[a[x].rson])
	{
//		cout << sum << endl;
		f[a[x].rson] = 1;
		cnt[sum+1]++;
		sd = max(sd, sum + 1);
		dfs(a[x].rson, sum + 1);
	}
}
struct node2{
	int x, v;
};
int bfs(int qd, int zd)
{
	queue<node2> q;
	clear
	f[qd] = 1;
	q.push({qd, 0});
	while (q.size())
	{
		node2 k = q.front();
		q.pop();
		if (k.x == zd)
		{
			return k.v;
		}
		if (a[k.x].father != -1 && !f[a[k.x].father])
		{
			f[a[k.x].father] = 1;
			q.push({a[k.x].father, k.v + 1});
		}
	}
}
int bfs2(int qd, int zd)
{
	queue<node2> q;
	clear
	f[qd] = 1;
	q.push({qd, 0});
	while (q.size())
	{
		node2 k = q.front();
		q.pop();
		if (k.x == zd)
		{
			return k.v;
		}
		if (a[k.x].lson != -1 && !f[a[k.x].lson])
		{
			f[a[k.x].lson] = 1;
			q.push({a[k.x].lson, k.v + 1});
		}
		if (a[k.x].rson != -1 && !f[a[k.x].rson])
		{
			f[a[k.x].rson] = 1;
			q.push({a[k.x].rson, k.v + 1});
		}
	}
}
void dfs_up(int v)
{
	if (a[v].father != -1 && !f[a[v].father])
	{
		f[a[v].father] = 1;
		if (a[v].father == y)
		{
			f_up = 1;
		}
		dfs_up(a[v].father);
	}
}
void dfs_down(int v)
{
	if (a[v].lson != -1 && !f[a[v].lson])
	{
		f[a[v].lson] = 1;
		dfs_down(a[v].lson);
	}
	if (a[v].rson != -1 && !f[a[v].rson])
	{
		f[a[v].rson] = 1;
		dfs_down(a[v].rson);
	}
} 

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		if (a[u].lson == -1)
		{
			a[u].lson = v;
		}
		else
		{
			a[u].rson = v;
		}
		a[v].father = u;
	}
	cin >> x >> y;
	f[1] = 1;
	cnt[1] = 1;
	dfs(1, 1);
	kd = 0;
	for (int i = 1; i <= sd; i++)
	{
//		cout << cnt[i] << ' ';
		kd = max(kd, cnt[i]);
	}
//	cout << endl;
	cout << sd << endl << kd << endl;
	clear
	dfs_up(x);
	clear
	dfs_down(y);
	if (f_up)
	{
		cout << bfs(x, y) * 2;
	}
	else if (f_down)
	{
		cout << bfs2(x, y);
	}
	else
	{
		cout << bfs(x, 1) * 2 + bfs2(1, y);
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...