18分求调!!!
查看原帖
18分求调!!!
960206
topcsa楼主2024/8/18 21:24
#include <bits/stdc++.h>
#define pushb push_back
using namespace std;
const int N = 110;
int dep[N], tdep;
int f[N][N];
int vis[N];
vector<int> g[N];
void dfs(int u, int fa, int op) {
	vis[u] = 1;
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	tdep = max(tdep, op);
	for (auto v : g[u]) {
		if (!vis[v] && v != fa) {
			dfs(v, u, op + 1);
		}
	}
	return ;
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int i = N; i >= 0; i--) {
		if (dep[u] - (1 << i) >= dep[v]) {
			u = f[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = N; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}
int width = -1e9;
queue<int> q;
void bfs(int x) {
	q.push(x);
	width = max(width, (int)q.size());
	memset(vis, 0, sizeof vis);
	vis[1] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
//		cout << u << ' ';
		for (int v : g[u]) {
			if (!vis[v]) {
				q.push(v);
				vis[v] = 1;
			}
		}
		width = max(width, (int)q.size());
	}
	return ;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pushb(v);
		g[v].pushb(u);
	}
	dfs(1, 0, 1);
	cout << tdep << '\n';
	bfs(1);
	cout << width << '\n';
	int x, y;
	cin >> x >> y;
	int lcas = lca(x, y);
	cout << dep[x] - lcas + dep[y] - lcas + 1;
	return 0;
}
2024/8/18 21:24
加载中...