@[lznxes](/user/953149) 你竟然没加注释?
注释版:
```cpp
#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 (fa[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]); //*2:向根节点,不*2:向叶子结点
}
int main()
{
int n,x,y,ma = INT_MIN,maxn = INT_MIN,a,b;//ma找深度最大,maxn找宽度最大
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; //标记当过儿子的为1,这里考虑根节点为1,先把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]]++; //c数组:标记深度为d[i]出现的次数
}
for (int i = 1;i <= ma;i++)
{
maxn = max(maxn,c[i]); //找c[i]最大值
}
cout << ma << endl << maxn << endl;
cout << dis(a,b);
return 0;
}
```
by lznxes @ 2024-04-14 16:11:29