题干：
给定一个有 n 个顶点的有向图，每个顶点有且仅有一条出边。每次询问给出两个顶点 ai 和 bi??，求满足以下条件的 xi?? 和 yi：
从顶点 aia_ia?i?? 沿出边走 xix_ix?i?? 步与从顶点 bi 沿出边走 yi 步到达的顶点相同时，max(xi,yi) 最小。
满足以上条件的情况下 min(xi,yi) 最小。
如果以上条件没有给出一个唯一的解，则还需要满足 xi≥yi??.
如果不存在这样的 xi 和 yi，则 xi=yi=−1.
题解：
首先，本题十分考验卡常技巧，不卡常会T得很惨。。。
1 const int L=1<<20|1; 2 char buffer[L],*S,*T; 3 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) 4 inline int read(){ 5 char a=getchar(); 6 int sum=0; 7 while(a<‘0‘||a>‘9‘) a=getchar(); 8 while(a>=‘0‘&&a<=‘9‘) sum=(sum<<1)+(sum<<3)+a-‘0‘,a=getchar(); 9 return sum; 10 }
来看一下题：
题中指出所有的路径都是单向的，而且每个点的出度都最多是1。我们将题中的的样例画一下，就可以发现这张图要么是普通的一棵树，要么是一个基环树（基环树是指其中只有一个环的一张比较特殊的图）。
又因为若所给数据是基环图，它也一定是一个内向图（所有非环路径最终一定汇入环中）。有了这些性质，我们可以建一个反图（方便求LCA）来跑。
若数据只是一棵树，在此就不再赘述（在下面都会涵盖）。
我们来考虑基环树：
它一定是由枝干（非环部分）与基环构成。
基环可以通过tarjan或dfs来求，毕竟是只有一个环，但作者在此建议大家用一用tarjan，比较方便标记环的大小与记录环上的节点。作者在此说的是标记环，而不是将环缩成点。这是因为在环中可能也需有所贡献，在下文也会有所重申。（注意要将环上的点标号）
而树上的枝干就可以用LCA来求，再加上 dfs求深度 + 节点间是否在同一基环树上 + 节点间是否在同一基环树的枝干上 ，正解的气息有没有问到。。。
上文中说到的 求节点间是否在同一基环树上、求节点间是否在同一基环树的枝干上 其实就是为了我们现在要讨论的节点位置关系有关。
其实两节点也只有以下几种可能关系：
1.两节点不在同一个树上（或图上）： 特判即可。
2.两节点在同一个树上（或图上）：
1‘.两节点在同一个树上的基环上：
用环的全长与两点的标号差相减的差值 与 两点的标号差作比较（环上的点的标号用到了）。
2’.两节点在同一个树上的同一枝干上： 倍增LCA求解。
（若数据只是一棵树，所有的操作几乎都用LCA就可解决）。
3‘.两节点在同一个树上的不同枝干上：
用dfs求出的deep（该节点到最近的环上的点的距离）+ 情况一的结果
这种情况注意有两种结果，注意看题干进行取舍。
本题在解决的时候将反图中的环看作根节点，而不是缩点，大大降低了时间复杂度与思考量（好像想到不缩点就挺有思维量的。。。）。dfs中的LCA与获得答案时的代码需认真。本题考查的十分全面。好题。。。
Code：
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #define $ 500111 5 using namespace std; 6 struct node{ int to,next; }a[$]; 7 int k,n,first[$],tot,dis[$],fa[$][21]; 8 int dep[$],dad[$],tar,dfn[$],lenc[$],belong[$],nex[$],cir[$],zh[$]; 9 inline void swap(int &x,int &y){ int t=x; x=y; y=t; } 10 inline int abs(int x) { return x<0?-x:x; } 11 inline int max(int x,int y) { return x>y?x:y; } 12 inline int min(int x,int y) { return x<y?x:y; } 13 const int L=1<<20|1; 14 char buffer[L],*S,*T; 15 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) 16 inline int read(){ 17 char a=getchar(); 18 int sum=0; 19 while(a<‘0‘||a>‘9‘) a=getchar(); 20 while(a>=‘0‘&&a<=‘9‘) sum=(sum<<1)+(sum<<3)+a-‘0‘,a=getchar(); 21 return sum; 22 } 23 inline void add(int x,int y){ 24 a[++tot]=(node){ y,first[x] }; 25 first[x]=tot; 26 } 27 inline void dfs(int x){ 28 for(register int i=first[x];i;i=a[i].next){ 29 int to=a[i].to; 30 if(cir[to]) continue; 31 dep[to]=dep[x]+1; 32 fa[to][0]=x; 33 belong[to]=belong[x]; zh[to]=zh[x]; 34 for(register int j=1;j<=20;++j) fa[to][j]=fa[fa[to][j-1]][j-1]; 35 dfs(to); 36 } 37 } 38 inline void tarjan(int x,int self){ 39 int to=nex[x]; dfn[x]=self; 40 if(dfn[to]==self){ 41 int tmp=x; 42 cir[tmp]=++tar; lenc[tar]++; 43 while(tmp!=dad[to]){ 44 lenc[tar]++; cir[tmp]=tar; 45 tmp=dad[tmp]; 46 } 47 } 48 else if(dfn[to]==0) dad[to]=x, tarjan(to,self); 49 } 50 inline int LCA(int x,int y){ 51 if(dep[x]<dep[y]) swap(x,y); 52 for(register int i=20;i>=0;--i) 53 if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; 54 if(x==y) return x; 55 for(register int i=20;i>=0;--i) 56 if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i]; 57 return fa[x][0]; 58 } 59 inline void renew(int x,int y,int xx,int yy,int &ans1,int &ans2){ 60 61 int out1=max(x,y),out2=max(xx,yy); 62 if(out1!=out2){ 63 if(out1<out2) ans1=x, ans2=y; 64 if(out1>out2) ans1=xx, ans2=yy; 65 return ; 66 } 67 out1=min(x,y), out2=min(xx,yy); 68 if(out1!=out2){ 69 if(out1<out2) ans1=x, ans2=y; 70 if(out1>out2) ans1=xx, ans2=yy; 71 return ; 72 } 73 if(x>=y) ans1=x, ans2=y; 74 if(x<y) ans1=xx, ans2=yy; 75 } 76 inline void solve(int x,int y){ 77 int ans1=0,ans2=0; 78 if(belong[x]!=belong[y]){ puts("-1 -1"); return ; } 79 if(zh[x]!=zh[y]){ 80 ans1=dep[x], ans2=dep[y]; 81 int p=zh[x],q=zh[y],i,j,ii,jj; 82 i=ii=ans1; j=jj=ans2; 83 int l=lenc[cir[zh[x]]],r=abs(dis[p]-dis[q]); 84 if(dis[p]>dis[q]) jj+=r, i+=l-r-1; 85 else jj+=l-r-1, i+=r; 86 renew(i,j,ii,jj,ans1,ans2); 87 printf("%d %d\n",ans1,ans2); return; 88 } 89 int lca=LCA(x,y); 90 ans1=dep[x]-dep[lca], ans2=dep[y]-dep[lca]; 91 printf("%d %d\n",ans1,ans2); 92 } 93 signed main(){ 94 n=read(), k=read(); 95 for(register int i=1,x;i<=n;++i) 96 x=read(), nex[i]=x, add(x,i); 97 for(register int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i); 98 for(register int i=1;i<=n;++i){ 99 if(cir[i]&&!dis[i]){ 100 int to=nex[i],now=1; 101 while(to!=i) dis[to]=now++,to=nex[to]; 102 } 103 } 104 for(register int i=1;i<=n;++i) 105 if(cir[i]) zh[i]=i, belong[i]=cir[i], dfs(i); 106 for(register int i=1,x,y;i<=k;++i) 107 x=read(), y=read(), solve(x,y); 108 }
约会 Rendezvous （基环树（内向） + tarjan缩点 + LCA）
原文：https://www.cnblogs.com/OI-zzyy/p/11172492.html
