【BZOJ 2791】 2791: [Poi2012]Rendezvous （环套树、树链剖分LCA）-白红宇

【BZOJ 2791】 2791: [Poi2012]Rendezvous （环套树、树链剖分LCA）

阅读量：5133 次

发布时间：2019-06-13

本文共 3573 字，大约阅读时间需要 11 分钟。

2791: [Poi2012]Rendezvous

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行，每行两个整数。

Sample Input

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

Sample Output

2 3
1 2
2 2
0 1
-1 -1

HINT

Source

【分析】

　　一开始以为是无向边ORZ。。

　　其实有向边只要改一点点东西。

　　那个x>=y是用来省掉SPJ的，不是题目要求

　　无向边的话，首先是一个基环森林，很明显是求最短路径然后除以二。

　　有向边的话，很多路径是固定的，

　　首先不是一个联通块的一定无法到达，是一个联通块的一定能到达（也许你觉得有向边不一定可以，但事实上是可以的，因为每个点只有一条出边的特殊性质）

　　这种特殊性质告诉我们：

　　环一定是通的，就是从环上任意一点走环一定能走回自己。

　　基环树下面的点的连边一定是向上的（考虑一个点只有一条出边，而环上的根的出边已经贡献给环了）

　　所以如果是同一棵树，那么求LCA，答案是唯一的。

　　如果不是，那么环上面也只有两种走法，两个答案比较一下即可。

　　【其实一开始看错题之后觉得边有向很难搞，其实知道性质就很简单了】

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 using namespace std;  7 #define Maxn 500010  8   9 int mymax(int x,int y) {
     return x>y?x:y;} 10 int mymin(int x,int y) {
     return x
            
             0?x:-x;} 12 13 struct node 14 { 15 int x,y,next,o; 16 bool p; 17 }t[Maxn*2];int len=0; 18 int first[Maxn]; 19 20 void ins(int x,int y) 21 { 22 t[++len].x=x;t[len].y=y; 23 t[len].next=first[x];first[x]=len; 24 t[len].p=1; 25 if(len%2==0) t[len].o=len-1; 26 else t[len].o=len+1; 27 } 28 29 int fa[Maxn],r1[Maxn],r2[Maxn]; 30 int ffa(int x) 31 { 32 if(x!=fa[x]) fa[x]=ffa(fa[x]); 33 return fa[x]; 34 } 35 36 int dis[Maxn]; 37 bool onc[Maxn]; 38 int dfs0(int x,int ff,int rr) 39 { 40 dis[x]=dis[ff]+1; 41 if(x==rr) {onc[x]=1;return 1;} 42 for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff) 43 { 44 int y=t[i].y,z=dfs0(y,x,rr); 45 if(z!=0) {t[i].p=t[t[i].o].p=0;onc[x]=1;return z+1;} 46 } 47 return 0; 48 } 49 50 int tp[Maxn],son[Maxn],sm[Maxn]; 51 int dep[Maxn],siz[Maxn],fd[Maxn]; 52 void dfs1(int x,int ff) 53 { 54 sm[x]=1;son[x]=0;fd[x]=ff; 55 for(int i=first[x];i;i=t[i].next) if(t[i].p&&t[i].y!=ff) 56 { 57 int y=t[i].y; 58 dis[y]=dis[x]; 59 dep[y]=dep[x]+1; 60 dfs1(y,x); 61 sm[x]+=sm[y]; 62 if(son[x]==0||sm[son[x]]
             
              dep[y]) swap(x,y); 85 // return dep[xx]+dep[yy]-2*dep[x]; 86 printf("%d %d\n",dep[xx]-dep[x],dep[yy]-dep[x]); 87 } 88 89 int main() 90 { 91 int n,q; 92 scanf("%d%d",&n,&q); 93 memset(first,0,sizeof(first)); 94 memset(r1,0,sizeof(r1)); 95 memset(onc,0,sizeof(onc)); 96 for(int i=1;i<=n;i++) fa[i]=i; 97 for(int i=1;i<=n;i++) 98 { 99 int x;100 scanf("%d",&x);101 if(ffa(x)==ffa(i))102 {103 r1[ffa(x)]=x;r2[ffa(x)]=i;104 }105 else106 {107 if(r1[ffa(x)]!=0) r1[ffa(i)]=r1[ffa(x)],r2[ffa(i)]=r2[ffa(x)];108 fa[ffa(x)]=ffa(i);109 ins(x,i);ins(i,x);110 }111 }112 for(int i=1;i<=n;i++) if(ffa(i)==i)113 {114 dis[r1[i]]=0;115 siz[i]=dfs0(r1[i],0,r2[i]);116 }117 for(int i=1;i<=n;i++) if(onc[i])118 {119 dep[i]=0;120 dfs1(i,0);121 dfs2(i,0,i);122 }123 for(int i=1;i<=q;i++)124 {125 int x,y;126 scanf("%d%d",&x,&y);127 if(ffa(x)!=ffa(y)) {printf("-1 -1\n");continue;}128 int sum;129 if(dis[x]!=dis[y])130 {131 sum=mymin(siz[ffa(x)]-myabs(dis[x]-dis[y]),myabs(dis[x]-dis[y]));132 int x1,y1,x2,y2;133 if(dis[x]
              
               mymax(x2,y2)) printf("%d %d\n",x2,y2);145 else146 {147 if(mymin(x1,y1)
               
                mymin(x2,y2)) printf("%d %d\n",x2,y2);149 else if(x1>=y1) printf("%d %d\n",x1,y1);150 else printf("%d %d\n",x2,y2);151 }152 }153 else ffind(x,y);154 }155 return 0;156 }