Description
给定一个n个顶点的有向图，每个顶点有且仅有一条出边。
对于顶点i，记它的出边为(i, a[i])。
再给出q组询问，每组询问由两个顶点a、b组成，要求输出满足下面条件的x、y：
1. 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。
2. 在满足条件1的情况下max(x,y)最小。
3. 在满足条件1和2的情况下min(x,y)最小。
4. 在满足条件1、2和3的情况下x>=y。
如果不存在满足条件1的x、y，输出-1 -1。
Input
第一行两个正整数n和q (n,q<=500,000)。
第二行n个正整数a[1],a[2],...,a[n] (a[i]<=n)。
下面q行，每行两个正整数a,b (a,b<=n)，表示一组询问。
Output
输出q行，每行两个整数。
思路：其实我觉得基环树题就是暴力模拟题……先找环，然后有多种情况，在环上某点的同一子树下，在环上不同子树下，不在同一联通块内，一一处理即可
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + ; int head[N], now;
struct edges{
int to, next, w;
}edge[N<<];
void add(int u, int v, int w){ edge[++now] = {v, head[u], w}; head[u] = now;}
void read(int &x){
int f=;x=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
x*=f;
} int n, q, dfn[N], sz, pre[N], tot, c[N], dict[N], bel[N], fa[N][], dep[N], pos[N];
vector<int> cir[N];
void fcur(int x){
dfn[x] = ++sz; bel[x] = tot;
for(int i = head[x]; i; i = edge[i].next){
int v = edge[i].to;
if(v == pre[x]) continue;
if(dfn[v]){
if(dfn[v] < dfn[x]) continue;
cir[tot].push_back(x); c[x] = tot;
for(; x != v; v = pre[v]){
cir[tot].push_back(v), c[v] = tot;
}
}else pre[v] = x, fcur(v);
}
return ;
} void dfs(int x, int father, int root){
dict[x] = root; fa[x][] = father;
for(int i = head[x]; i; i = edge[i].next){
int v = edge[i].to;
if(v == father || c[v]) continue;
dep[v] = dep[x] + ;
dfs(v, x, root);
}
}
int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int k=dep[u]-dep[v];
for(int i=;i<=;i++)
if((<<i)&k) u=fa[u][i];
if(u==v) return u;
for(int i=;i>=;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][];
}
void dfs2(int x, int step){
pos[x] = step;
for(int i = head[x]; i; i = edge[i].next){
int v = edge[i].to;
if(edge[i].w && !pos[v]) dfs2(v, step + );
}
}
int main(){
read(n), read(q);
int x, y;
for(int i = ; i <= n; i++){
read(x);
add(i, x, ), add(x, i, );
}
for(int i = ; i <= n; i++){
if(!dfn[i]){
sz = ; tot++;
fcur(i);
}
}
for(int i = ; i <= tot; i++){
dfs2(cir[i][], );
for(int j = ; j < cir[i].size(); j++){
x = cir[i][j];
dict[x] = x;
dfs(x, x, x);
}
}
for(int j = ; j <= ; j++)
for(int i = ; i <= n; i++)
fa[i][j + ] = fa[fa[i][j]][j];
while(q--){
scanf("%d%d", &x, &y);
if(bel[x] != bel[y]){
puts("-1 -1"); continue;
}else if(dict[x] == dict[y]){
int lca = LCA(x, y);
printf("%d %d\n", dep[x] - dep[lca], dep[y] - dep[lca]);
}else{
int rt1 = dict[x], rt2 = dict[y], siz = cir[bel[x]].size();
int s1 = dep[x] - dep[rt1], s2 = dep[y] - dep[rt2];
int k1, k2;
if(pos[rt1] < pos[rt2]) k1 = pos[rt2] - pos[rt1], k2 = siz - k1;
else k2 = pos[rt1] - pos[rt2], k1 = siz - k2;
int tmp1 = s1 + k1, tmp2 = s2 + k2;
if(max(tmp1, s2) != max(s1, tmp2)){
if(max(tmp1, s2) > max(s1, tmp2)) printf("%d %d\n", s1, tmp2);
else printf("%d %d\n", tmp1, s2);
continue;
}
else if(min(tmp1, s2) != min(s1, tmp2)){
if(min(tmp1, s2) > min(s1, tmp2)) printf("%d %d\n", s1, tmp2);
else printf("%d %d\n", tmp1, s2);
continue;
}
else{
if(tmp1 >= s2) printf("%d %d\n", tmp1, s2);
else printf("%d %d\n", s1, tmp2);
}
}
}
return ;
}