LCA 10pts 求助, 路过dalao帮忙看看(跪求
查看原帖
LCA 10pts 求助, 路过dalao帮忙看看(跪求
519384
Link_Cut_Y楼主2021/10/2 20:22

码风略丑,请见谅

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 110, M = N << 2;

int h[N], e[M], ne[M], idx;
int n;
int f[N][20];
int dep[N];
bool st[N];
int ans[N];
int max_depth, max_width;
int width[N];

void add(int a, int b)
{
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs(int u, int fa)
{
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	width[u] = dep[u];
	max_depth = max(max_depth, width[u]);
	st[u] = true;
	
	for (int i = h[u]; i; i = ne[i])
		if (!st[e[i]]) dfs(e[i], u);
}

int find(int a, int b)
{
	if (dep[a] > dep[b]) swap(dep[a], dep[b]);
	for (int i = 11; i >= 0; i -- )
		if (dep[f[a][i]] >= dep[b]) a = f[a][i];
		
	if (a == b) return a;
	for (int i = 11; i >= 0; i -- )
		if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
		
	return f[a][0];
}

int main()
{
	cin >> n;
	
	for (int i = 1; i < n; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	
	dfs(1, 0);
	
	int x, y;
	scanf("%d%d", &x, &y);
	
	int mem[N] = {0};
	
	for (int i = 1; i <= n; i ++ ) ans[dep[i]] ++ ;
	for (int i = 1; i <= max_depth; i ++ ) max_width = max(max_width, ans[i]);
	
	cout << max_depth << endl << max_width << endl;
	
	int lca = find(x, y);
	cout << 2 * (dep[x] - dep[lca]) + (dep[y] - dep[lca]);
}
2021/10/2 20:22
加载中...