题目

求两点的最近公共祖先

---

分析

由于询问次数少，于是就只打Tarjan（不是求强联通分量的）懒

---

代码

#include <cstdio> using namespace std; struct node{short y,next;}e[20001]; int t; short n,ok,q,p,m,x,y,ls[10001],in[10001],v[10001],f[10001]; void add(int x,int y){e[++m].y=y; e[m].next=ls[x]; ls[x]=m;} int getf(int u){return (f[u]==u)?u:getf(f[u]);} void tarjan(int x){ v[x]=1; for (int i=ls[x];i;i=e[i].next){ if (v[e[i].y]) continue; tarjan(e[i].y); f[e[i].y]=x; } if (ok) return; if (v[q]==2&&x==p){ printf("%d\n",getf(q)); ok=1; return; } if (v[p]==2&&x==q){ printf("%d\n",getf(p)); ok=1; return; } v[x]=2; } int main(){ scanf("%d",&t); while (t--){ scanf("%d",&n); m=ok=0; for (int i=1;i<=n;i++) ls[i]=in[i]=v[i]=0,f[i]=i; for (int i=1;i<n;i++) scanf("%d%d",&x,&y),in[y]++,add(x,y),add(y,x); scanf("%d%d",&q,&p); for (int i=1;i<=n;i++) if (!in[i]) tarjan(i); } return 0; }