#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define maxn 202
using namespace std;
int now,head[maxn],n,m,s,d[maxn],deep[maxn],p[maxn][11],maxx;
struct node{
int a,b,next;
}e[maxn];
inline void add(int u,int s)
{
e[++now].a=u;
e[now].b=s;
e[now].next=head[u];
head[u]=now;
} emmm链式前向星存图标准代码了解一下
inline void dfs(int k,int fa)
{
d[k]=d[fa]+1;子节点的层数只其父节点层数+1
deep[k]=d[k];
maxx=max(maxx,d[k]);统计最大层数
p[k][0]=fa;
for(int i=1;(1<<i)<=d[k];i++)
{
p[k][i]=p[p[k][i-1]][i-1];倍增的关键!!!
}
for(int i=head[k];i;i=e[i].next)
{
int b=e[i].b;
if(b!=fa) dfs(b,k); 如果没有处理过,就跑一边 dfs的思想
}
}倍增标准预处理
inline int lca(int a,int lp)
{
if(d[a]>d[lp]) swap(a,lp);
for(int i=10;i>=0;i--)因为数据很水便只开了10就够用了
{
if(d[a]<=d[lp]-(1<<i))
{
lp=p[lp][i];先让两个点的层数爬到一起
}
}
if(a==lp) return a;
for(int i=10;i>=0;i--)
{
if(p[a][i]!=p[lp][i])
a=p[a][i],lp=p[lp][i];然后就是两个点一起爬树
}
return p[a][0];因为现在都是相等的所以随便输出哪一个都可以了
}
int main()
{
int maxl=0,cs[105]={0},x,y;
scanf("%d",&n);
For(i,1,n-1)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x); 无向图别忘了
}
dfs(1,0);
scanf("%d%d",&x,&y);
For(i,1,n) cs[deep[i]]++;统计宽度
For(i,1,maxx) maxl=max(maxl,cs[i]);
printf("%d\n%d\n",maxx,maxl);
int kjk=lca(x,y);
printf("%d\n",(d[x]-d[kjk])*2+(d[y]-d[kjk]));emmm这里是因为数据水到都是先父节点再子节点所以我就懒得打一个max函数了,只要记得乘以二就可以了
return 0;
}