题目链接：点击打开链接
题目大意：给出中序序列和先序序列，再给出两个点，求这两个点的最近公共祖先。
解题思路：不用建树～已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点，在此时并入lca算法可以确定两个结点的公共祖先～
注意：题目中 n 才是结点个数；pos 不能用数组开，因为存储位置的是利用该结点的值而不是下标，所以用ump。
AC 代码1（未建树版）
usingnamespacestd; typedeflonglongll; constintmaxn=1e4+10; intin[maxn], pre[maxn]; unordered_map<int,int>pos; voidlca(intinl,intinr,intprel,inta,intb) { if(inl>inr) return; intinRt=pos[pre[prel]], aIn=pos[a], bIn=pos[b]; if(inRt>aIn&&inRt<bIn||inRt<aIn&&inRt>bIn) printf("LCA of %d and %d is %d.\n", a, b, in[inRt]); elseif(aIn==inRt||bIn==inRt) printf("%d is an ancestor of %d.\n", in[inRt], aIn==inRt?b : a); elseif(aIn>inRt&&bIn>inRt) lca(inRt+1,inr,prel+1+(inRt-inl),a,b); elseif(aIn<inRt&&bIn<inRt) lca(inl,inRt-1,prel+1,a,b); } intmain() { intq,n,a,b; scanf("%d%d",&q,&n); for(inti=1;i<=n;i++) scanf("%d",&in[i]), pos[in[i]]=i; for(inti=1;i<=n;i++) scanf("%d",&pre[i]); while(q--) { scanf("%d%d",&a,&b); if(pos[a]==0&&pos[b]==0) printf("ERROR: %d and %d are not found.\n", a, b); elseif(pos[a]==0||pos[b]==0) printf("ERROR: %d is not found.\n", pos[a] ==0?a : b); elselca(1,n,1,a,b); } return0; }
AC 代码2（建树-搜索版）
usingnamespacestd; typedeflonglongll; constintmaxn=1e4+10; structnode{ intd,l,r; }T[maxn]; unordered_map<int,int>vis; intin[maxn], pre[maxn]; intcreate(intl1,intr1,intl2,intr2) // in pre{ if(l1>r1) return-1; intrt=l2; intp1=l1,p2; while(in[p1]!=pre[rt]) p1++; p2=p1-l1; T[rt].d=pre[rt]; T[rt].l=create(l1,p1-1,l2+1,l2+p2); T[rt].r=create(p1+1,r1,l2+p2+1,r2); returnrt; } intlca(intrt,inta,intb) { if(rt==-1) return-1; if(a==T[rt].d||b==T[rt].d) returnrt; intleft=lca(T[rt].l,a,b); intright=lca(T[rt].r,a,b); if(left!=-1&&right!=-1) returnrt; returnleft==-1?right : left; } intmain() { intn,q,a,b; scanf("%d%d",&q,&n); for(inti=0;i<n;i++) scanf("%d",&in[i]), vis[in[i]]=1; for(inti=0;i<n;i++) scanf("%d",&pre[i]); intrt=create(0,n-1,0,n-1); while(q--) { scanf("%d%d",&a,&b); if(!vis[a] &&!vis[b]) printf("ERROR: %d and %d are not found.\n",a,b); elseif(!vis[a] ||!vis[b]) printf("ERROR: %d is not found.\n",!vis[a]?a:b); else { intminRt=lca(rt,a,b); if(T[minRt].d==a||T[minRt].d==b) printf("%d is an ancestor of %d.\n",T[minRt].d,T[minRt].d==a?b:a); elseprintf("LCA of %d and %d is %d.\n",a,b,T[minRt].d); } } return0; }
AC 代码3（建树-LCA版）
usingnamespacestd; typedeflonglongll; constintmaxn=1e4+10; structnode{ intd,l,r; }T[maxn]; unordered_map<int,int>vis, lvl, fu; intin[maxn], pre[maxn]; intcreate(intl1,intr1,intl2,intr2,intl,intf) // in pre{ if(l1>r1) return-1; intrt=l2; intp1=l1,p2; while(in[p1]!=pre[rt]) p1++; p2=p1-l1; T[rt].d=pre[rt]; lvl[pre[rt]]=l; fu[pre[rt]]=f; T[rt].l=create(l1,p1-1,l2+1,l2+p2,l+1,pre[rt]); T[rt].r=create(p1+1,r1,l2+p2+1,r2,l+1,pre[rt]); returnrt; } intlca(inta,intb) { introot; if(a==b) returna; if(fu[a]==fu[b]) returnfu[a]; if(lvl[a]>lvl[b]) root=lca(fu[a],b); elseroot=lca(a,fu[b]); if(root!=-1) returnroot; return-1; } intmain() { intn,q,a,b; scanf("%d%d",&q,&n); for(inti=0;i<n;i++) scanf("%d",&in[i]), vis[in[i]]=1; for(inti=0;i<n;i++) scanf("%d",&pre[i]); intrt=create(0,n-1,0,n-1,1,-1); while(q--) { scanf("%d%d",&a,&b); if(!vis[a] &&!vis[b]) printf("ERROR: %d and %d are not found.\n",a,b); elseif(!vis[a] ||!vis[b]) printf("ERROR: %d is not found.\n",!vis[a]?a:b); else { intminRt=lca(a,b); if(minRt==a||minRt==b) printf("%d is an ancestor of %d.\n",minRt,minRt==a?b:a); elseprintf("LCA of %d and %d is %d.\n",a,b,minRt); } } return0; }
