题目链接：Luogu P3884、JLOI2009。

未完待续

题解

思路

倍增求 \(\texttt{LCA}\) 裸题。

代码

渐进时间复杂度 \(\Theta(n\log _ 2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100+5;
const int MAXLOG2N=7+1;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n;
int cnt,head[MAXN],to[MAXN<<1],Next[MAXN<<1];

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

inline void Read(void){
    n=read();
    for(reg int i=1;i<n;++i){
        static int u,v;
        u=read(),v=read();
        Add_Edge(u,v);
        Add_Edge(v,u);
    }
    return;
}

int dep[MAXN];
int fa[MAXN][MAXLOG2N];

inline void DFS(reg int ID,reg int father){
    fa[ID][0]=father;
    dep[ID]=dep[father]+1;
    for(reg int i=1;i<MAXLOG2N;++i)
        fa[ID][i]=fa[fa[ID][i-1]][i-1];
    for(reg int i=head[ID];i;i=Next[i])
        if(to[i]!=father)
            DFS(to[i],ID);
    return;
}

inline int LCA(int x,int y){
    if(dep[x]>dep[y])
        swap(x,y);
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(dep[fa[y][i]]>=dep[x])
            y=fa[y][i];
    if(x==y)
        return x;
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int T[MAXN];

inline void Work(void){
    DFS(1,0);
    int Maxdep=1,Maxwid=1;
    for(reg int i=1;i<=n;++i){
        ++T[dep[i]];
        Maxdep=max(Maxdep,dep[i]);
        Maxwid=max(Maxwid,T[dep[i]]);
    }
    reg int u=read(),v=read();
    printf("%d\n%d\n%d\n",Maxdep,Maxwid,(dep[u]<<1)+dep[v]-(dep[LCA(u,v)]*3));
    return;
}