[POI2012] Rendezvous 题解

众所周知，\(lyh\) 是一名压行大师，也是一名 \(juruo\)，所以他将他繁琐的方法用 \(102\) 行表现了出来……

明显原题为基环内向树森林。

首先用并查集计算连通块，不在一个连通块里的答案就是 \(-1\ -1\)。

发现实际上答案就是以环为根节点，求 \(lca\) 的结果，求完后可以分为两种情况：

1. 根节点不在环上。
   明显答案就是两个点向上跳的次数。
2. 根节点在环上。
   发现答案有且仅有两种情况：\(a\) 找 \(b\)、\(b\) 找 \(a\)。
   显然想到分别尝试两种可能性，按题目流程比较优劣。

有一个优化判环的方法：

在进行并查集时，无条件将 \(i\) 置于 \(a_i\) 下。这样可以保证每个根节点都在环上，使判环更便捷、更迅速。

时间复杂度瓶颈为并查集和排序算法。时间复杂度 \(O(n\log n+q\log q)\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,q,m,h[N],to[N],nxt[N];
int l=1,cnt,lp[N],lpv[N],fh[N];
int dep[N],f[N][23],t[N];
struct que{
    int a,b,ij,id;
    int ans1,ans2;
}qu[N];
int cmp(que x,que y){
    return x.id<y.id;
}int cmp2(que x,que y){
    return x.ij<y.ij;
}void init(){
    for(int i=1;i<=n;i++)
        fh[i]=i;
}int find(int x){
    if(fh[x]==x) return x;
    return fh[x]=find(fh[x]);
}void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    fh[y]=x;
}void add(int x,int y){
    to[++m]=y;
    nxt[m]=h[x];
    h[x]=m;
}void dfs_lca(int x,int ft,int z){
    f[x][0]=ft;lpv[x]=z;
    dep[x]=dep[ft]+1;
    for(int i=0;i<22;i++)
        f[x][i+1]=f[f[x][i]][i];
    for(int i=h[x];i;i=nxt[i])
        if(to[i]!=ft) dfs_lca(to[i],x,z);
}int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=22;~i;i--)
        if(dep[x]-dep[y]>=(1<<i))
            x=f[x][i];
    if(x==y) return x;
    for(int i=22;~i;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}int cmp3(int a,int b,int c,int d){
    if(max(a,d)!=max(b,c))
        return max(a,d)>max(b,c);
    if(min(a,d)!=min(b,c))
        return min(a,d)>min(b,c);
    return a<d;
}void solve(int rt){
    cnt=0;
    int x=rt,y=t[rt];
    lp[++cnt]=y;
    lpv[y]=cnt;
    while(y!=x){
        lp[++cnt]=t[y];
        lpv[t[y]]=cnt;
        y=t[y];
    }for(int i=1;i<=cnt;i++)
        for(int j=h[lp[i]];j;j=nxt[j])
            if(!lpv[to[j]]&&to[j]!=lp[i])
                dfs_lca(to[j],lp[i],i);
    while(rt==qu[l].id){
        int a=qu[l].a,b=qu[l].b;
        int lc=lca(a,b);
        qu[l].ans1=dep[a]-dep[lc];
        qu[l].ans2=dep[b]-dep[lc];
        if(lc){l++;continue;}
        int ab=abs(lpv[a]-lpv[b]);
        int cd=cnt-ab;
        if(lpv[a]>lpv[b]) swap(ab,cd);
        int aa=qu[l].ans1,bb=qu[l].ans2;
        int cc=aa+ab,dd=bb+cd;
        if(cmp3(aa,bb,cc,dd))
            qu[l++].ans1=cc;
        else qu[l++].ans2=dd;
    }
}int main(){
    scanf("%d%d",&n,&q);init();
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
        add(t[i],i);
        unite(t[i],i);
    }for(int i=1;i<=q;i++){
        scanf("%d%d",&qu[i].a,&qu[i].b);
        qu[i].ij=i;
        if(find(qu[i].a)!=find(qu[i].b)){
            qu[i].ans1=qu[i].ans2=-1;
            qu[i].id=1e9;continue;
        }qu[i].id=find(qu[i].a);
    }sort(qu+1,qu+q+1,cmp);
    for(int i=1;i<=n;i++)
        if(find(i)==i) solve(i);
    sort(qu+1,qu+q+1,cmp2);
    for(int i=1;i<=q;i++)
        printf("%d %d\n",qu[i].ans1,qu[i].ans2);
    return 0;
}