1 int n,m,hcnt,qcnt; 2 int head[maxn],query[maxn],vis[maxn]; 3 int anc[maxn],fp[maxn],indu[maxn],ans[N]; 4 struct Node{ 5 int to,next; 6 }node[maxn]; 7 struct Query{ 8 int to,next,index; 9 }que[N]; 10 int findp(int x){return fp[x]==x?x:fp[x]=findp(fp[x]);} 11 inline void init(){ 12 mst(anc,0);mst(indu,0);mst(num,0); 13 mst(head,-1);mst(query,-1);mst(vis,0); 14 mst(ans,0);hcnt=qcnt=0; 15 } 16 inline void add(int x,int y){ 17 node[hcnt].to=y;node[hcnt].next=head[x]; 18 head[x]=hcnt++; 19 } 20 inline void addq(int x,int y,int i){ 21 que[qcnt].to=y;que[qcnt].next=query[x]; 22 que[qcnt].index=i;query[x]=qcnt++; 23 } 24 void Un(int x,int y){ 25 int xx=findp(x),yy=findp(y); 26 if(xx!=yy) fp[xx]=yy; 27 } 28 void dfs(int x){ 29 vis[x]=1;fp[x]=x; 30 for(int i=head[x];~i;i=node[i].next){ 31 int e=node[i].to; 32 if(vis[e])continue; 33 dfs(e); 34 Un(x,e); 35 anc[findp(x)]=x; 36 } 37 for(int i=query[x];~i;i=que[i].next){ 38 int e=que[i].to; 39 if(vis[e]){ 40 ans[que[i].index]=anc[findp(e)]; 41 } 42 } 43 }