wa#5#6QAQ,求调
查看原帖
wa#5#6QAQ,求调
1548725
xiaII楼主2025/1/4 16:16
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
const int N = 1e3;
vector<int>g[N];
int dep[N]; int fa[N][25]; int cdep[N];
void dfs(int u, int f) {
	dep[u] = dep[f] + 1;
	cdep[dep[u]]++;
	fa[u][0] = f;
	for (int i = 1; i <= 20; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (const auto& x : g[u]) {
		if (x == f)continue;
		dfs(x, u);
	}
}
int lca(int x, int y) {
	if (dep[x] < dep[y])swap(x, y);
	for (int i = 20; i >= 0; i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y)return x;
	for (int i = 20; i >= 0; i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[x][i];
		}
	}
	return fa[x][0];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 0);
	int x, y; cin >> x >> y;
	sort(cdep + 1, cdep + 1 + n, greater<int>());
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (ans < dep[i])
			ans = dep[i];
	}
	cout << ans << endl << cdep[1] << endl;
	cout << (dep[x] - dep[lca(x, y)]) * 2 + dep[y] - dep[lca(x, y)];
	return 0;
}
2025/1/4 16:16
加载中...