题目链接: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; }
近期评论