我口胡的二叉树
查看原帖
我口胡的二叉树
558597
MujicaSaki摸鱼楼主2022/7/12 18:01

照着题解写的,MLE了

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1005],d[1005],t,h[1005],s,k,g,p[1005];
struct node
{
    int a,b;
}e[1005];
void j(int x,int y)
{
    e[++t].a=y;
    e[t].b=h[x];
    h[x]=t;
}
void dfs(int x,int y)
{
    f[x]=y;
    d[x]=d[y]+1;
    for(int i=h[x];i>0;i=e[i].b) if(e[i].a!=y) dfs(e[i].a,x);
}
int lca(int x,int y)
{
    while(x!=y)
    {
        if(d[x]>=d[y]) x=f[x];
        else y=f[y];
    }
    return x;
}
int x,y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        j(x,y);
        j(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        g=max(d[i],g);
        p[d[i]]++;
    }
    for(int i=1;i<=g;i++) k=max(k,p[i]);
    cin>>x>>y;
    cout<<g<<endl<<k<<endl<<(d[x]-d[lca(x,y)])*2+d[y]-d[lca(x,y)];
}
2022/7/12 18:01
加载中...