这是很多个环套树，然后理解了题意lca+乱搜什么的…
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;const int maxn = 510000;const int maxb = 21;struct edge{ int y,nex; edge(){} edge(int _y,int _nex){y=_y;nex=_nex;}}a[maxn]; int len,fir[maxn];void ins(int x,int y){a[++len]=edge(y,fir[x]); fir[x]=len;}int n,q,_to[maxn];int fa[maxn];int find_(int x){ if(fa[x]==x) return x; return fa[x]=find_(fa[x]);}int bel[maxn],id;bool v[maxn];int c_sum[maxn],c_id[maxn];int sta[maxn],tp;void f_c(int x){ if(v[x]) { int cid=0; int la=0; while(la!=x) { la=sta[tp--]; c_sum[bel[x]]++; c_id[la]=++cid; } return ; } v[x]=true; sta[++tp]=x; f_c(_to[x]);}int tid[maxn],f[maxn][maxb],dep[maxn];void dfs(int x,int rt){ tid[x]=rt; for(int i=1;i<maxb;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(!c_id[y]) { f[y][0]=x; dep[y]=dep[x]+1; dfs(y,rt); } }}int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=maxb-1;i>=0;i--) if(dep[x]-(1<<i)>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=maxb-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];}int main(){ memset(fir,0,sizeof fir); len=0; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); ins(x,i); _to[i]=x; fa[find_(x)]=fa[find_(i)]; } memset(bel,0,sizeof bel); id=0; for(int i=1;i<=n;i++) bel[i]=find_(i); memset(c_sum,0,sizeof c_sum); memset(v,false,sizeof v); for(int i=1;i<=n;i++) if(!c_sum[bel[i]]) tp=0,f_c(i); for(int i=1;i<=n;i++) if(c_id[i]) { dep[i]=0; dfs(i,i); } while(q--) { int a1,a2; int x,y; scanf("%d%d",&x,&y); if(bel[x]!=bel[y]){ PRintf("-1 -1/n"); continue; } if(tid[x]!=tid[y]) { a1=dep[x]; a2=dep[y]; x=tid[x]; y=tid[y]; int tmp=abs(c_id[x]-c_id[y]); int t1,t2; t1=c_id[x]>c_id[y]?c_sum[bel[x]]-tmp:tmp; t2=c_id[x]>c_id[y]?tmp:c_sum[bel[x]]-tmp; swap(t1,t2); if(t1&&t2) { if(a1+t1==a2+t2) { if(a1>=a2) a1+=t1; else a2+=t2; } else if(a1+t1>a2+t2) a2+=t2; else a1+=t1; } printf("%d %d/n",a1,a2); } else { int LCA=lca(x,y); a1=dep[x]-dep[LCA]; a2=dep[y]-dep[LCA]; printf("%d %d/n",a1,a2); } } return 0;}新闻热点
疑难解答
