Main » 2013 October 11 » LCA模版
5:38 AM LCA模版 |
数组模拟链表+ST-RMQ#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define N 300010 #define M 40 typedef long long LL; using namespace std; int dep,L,pre[N],last[N],size[N],e[N],len=0,f[N],D[N],p[N],dp[N][M],n,flag[N]; void add(int u,int v) { pre[++len]=last[u]; last[u]=len;e[len]=v; size[u]++; } void RMQ_init(int n) { int i,j; for (i=1;i<=n;i++) dp[i][0]=D[i]; int m=floor(log(n*1.0)/log(2.0)); for (j=1;j<=m;j++) for (i=1;i<=n-(1<<j)+1;i++) dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int RMQ(int l,int r) { int k=floor(log((r-l+1)*1.0)/log(2.0)); return min(dp[l][k],dp[r-(1<<k)+1][k]); } int LCA(int x,int y) { int px=p[x],py=p[y]; if (px>py) {int t=px;px=py;py=t;} return f[RMQ(px,py)]; } void DFS(int x,int P) { int tmp=++dep; D[++L]=tmp;f[tmp]=x;p[x]=L; int pos=last[x]; int i; FOR(i,1,size[x]) { int v=e[pos]; if (v==P) continue; DFS(v,x); D[++L]=tmp; pos=pre[pos]; } } int main() { scanf("%d",&n); memset(flag,0,sizeof(flag)); int i,u,v; FOR(i,1,n-1) { scanf("%d %d",&u,&v); add(u,v);add(v,u);flag[v]=1; } int R; FOR(i,1,n) if (!flag[i]) {R=i;break;} L=0,dep=0; DFS(R,-1); RMQ_init(L); int m; scanf("%d",&m); FOR(i,1,m) { scanf("%d %d",&u,&v); printf("%d\n",LCA(u,v)); } } |
|
|
| Total comments: 0 | |