原题链接
加了所有能加的优化 还是70分 简直绝望
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> using namespace std; int n,m,s,ans,f[500000+5][20],deep[500000+5],head[500000+5],nxt[1000000+5],num[1000000+5],tot; inline int Read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return x*f; } void add(int x,int y) { tot++; num[tot]=y; nxt[tot]=head[x]; head[x]=tot; } void dfs1(int p) { int i; for(i=head[p];i;i=nxt[i]) if(!f[num[i]][0]) { f[num[i]][0]=p; deep[num[i]]=deep[p]+1; dfs1(num[i]); } } void dfs2() { int i,j; for(j=1;(1<<j)<=n;j++) for(i=1;i<=n;i++) if(f[i][j-1]!=-1) f[i][j]=f[f[i][j-1]][j-1]; } int lca(int k1,int k2) { int i; if(deep[k1]>deep[k2]) swap(k1,k2); while(deep[k1]!=deep[k2]) k2=f[k2][0]; if(k1==k2) return k1; for(i=0;(1<<i)<=deep[k1];i++); i--; int x=i; for(i=x;i>=0;i--) if(f[k1][i]!=-1&&f[k1][i]!=f[k2][i]) { k1=f[k1][i]; k2=f[k2][i]; } return f[k1][0]; } int main() { int i,x,y,a,b; n=Read(); m=Read(); s=Read(); for(i=1;i<n;i++) { x=Read(); y=Read(); add(x,y); add(y,x); } f[s][0]=-1; dfs1(s); dfs2(); for(i=1;i<=m;i++) { a=Read(); b=Read(); ans=lca(a,b); printf("%d\n",ans); } return 0; }