#1玄关
查看原帖
#1玄关
953149
DoubleQLzn楼主2024/4/14 15:52
#include <bits/stdc++.h>
using namespace std;
int l[105],r[105],fa[105],f[105],d[105],c[105];
vector<int> son[105];
int LCA(int x,int y)
{
	memset(f,0,sizeof f);
	while (x != 0)
	{
		x = fa[x];		
		f[x] = 1;
	}
	while (f[y] == 0)
	{
		y = fa[y];
 	} 
 	if (y == 0) return 1;
 	return y;
}
int dis(int x,int y)
{
	int t = LCA(x,y);
	return (d[x] - d[t]) * 2 + (d[y] - d[t]);  
}
int main()
{
	int n,x,y,ma = INT_MIN,maxn = INT_MIN,a,b;
	cin >> n;
	for (int i = 1;i < n;i++)
	{
		cin >> x >> y;
		son[x].push_back(y);
		son[y].push_back(x);
	}
	cin >> a >> b;
	l[1] = son[1][0],f[son[1][0]] = 1,fa[son[1][0]] = 1;
	r[1] = son[1][1],f[son[1][1]] = 1,fa[son[1][0]] = 1;
	for (int i = 2;i <= n;i++)
	{
		if (f[i] == 1) 
		{
			for (auto s : son[i])
			{
				if (f[s] == 0 && s != 1)
				{
					if (!l[i]) 
					{
						l[i] = s;
						fa[s] = i;
					}
					else 
					{
						r[i] = s;
						fa[s] = i;
					}
					f[s] = 1;
				}
			}
		}
	}
	d[1] = 1;
	for (int i = 1;i <= n;i++)
	{
		if (l[i] != 0) d[l[i]] = d[i] + 1;
		if (r[i] != 0) d[r[i]] = d[i] + 1;
		ma = max(ma,d[i]);
		c[d[i]]++;
	}
	for (int i = 1;i <= ma;i++)
	{
		maxn = max(maxn,c[i]); 
	}
	cout << ma << endl << maxn << endl; 
	cout << dis(a,b);
	return 0;
}

#1过不去,深度不对,因为不能用递推,用DFS吗?

2024/4/14 15:52
加载中...