【洛谷P3398】仓鼠找sugar

画个图就能多少看出些规律

证明借鉴一下大牛的题解：

设从A到B，经过的深度最小的点为X 同理，C,D的为Y

题目是一个点从A出发到B 一个从C出发到D

那么从A到B可以分解成先从A到X 再从X到B。。。 C同理

假设能相遇那么

要么在A到X的过程A,B相遇要么在X到B的过程A,B相遇

对于在A到X的过程相遇的情况又可以分解为：

情况1：

在A到X的过程和 C到Y的过程中A,B相遇此时相遇点的深度必然大于等于MIN（X深度，Y深度）

情况2：

在A到X的过程和 Y到D的过程中A,B相遇此时相遇点的深度必然大于等于MIN （X深度，Y深度）

另一种情况同理。。。

所以显然只要求出MIN=min(lca(a,b),lca(c,d));(lca返回的是两个点公共祖先的最大深度)

假如lca(a,c) lca(a,d) lca(b,c) lca(b,d) 中有任意一个大于等于MIN 的话那么可以相遇否则不能

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,p=;

 int n,q,size,father[N][p+],head[M];

 int nxt[M],son[M],deep[N];

 int read(){

     int sum=;

     char ch=getchar();

     while (ch<''||ch>'')

         ch=getchar();

     while (ch>=''&&ch<=''){

         sum=sum*+ch-'';

         ch=getchar();

     }

     return sum;

 }

 void uni(int x,int y){

     size++;

     nxt[size]=head[x];

     head[x]=size;

     son[size]=y;

 }

 void swap(int &a,int &b){

     int tmp=a;

     a=b;

     b=tmp;

 }

 void dfs(int fa,int x){

     for (int k=head[x];k;k=nxt[k]){

         int y=son[k];

         if (y==fa)

             continue;

         father[y][]=x;

         deep[y]=deep[x]+;

         dfs(x,y);

     }

 }

 void pre(){

     for (int j=;j<=p;j++)

         for (int i=;i<=n;i++)

             father[i][j]=father[father[i][j-]][j-];

 }

 int LCA(int x,int y){

     if (deep[x]<deep[y])

         swap(x,y);

     int d=deep[x]-deep[y];

     for (int j=p;j>=;j--)

         if (d&(<<j))

             x=father[x][j];

     if (x==y)

         return x;

     for (int j=p;j>=;j--)

         if (father[x][j]!=father[y][j]){

             x=father[x][j];

             y=father[y][j];

         }

     return father[x][];

 }

 int main(){

     int u,v;

     size=;

     n=read();

     q=read();

     for (int i=;i<n;i++){

         u=read();

         v=read();

         uni(u,v);

         uni(v,u);

     }

     deep[]=;

     for (int i=;i<=n;i++)

         father[i][]=i;

     dfs(,);

     pre();

     int a,b,c,d;

     for (int i=;i<=q;i++){

         a=read();

         b=read();

         c=read();

         d=read();

         int lca=max(deep[LCA(a,b)],deep[LCA(c,d)]);

         int l1=max(deep[LCA(a,c)],deep[LCA(a,d)]);

         int l2=max(deep[LCA(b,c)],deep[LCA(b,d)]);

         if (max(l1,l2)>=lca)

             printf("Y\n");

         else

             printf("N\n");

     }

     return ;

 }

当然我们也可以判断一下最深的LCA是否在较浅的LCA路径之外

（比如lca_min=lca(a,b),则若deep[a]<lca_max&&deep[b]<lca_max(=lca(c,d))就在外面）

在外面肯定不能相遇

否则再判断一下它是否在其路径上

判断方法，，倍增跳点即可

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N=,M=,p=;

 int n,q,size,father[N][p+],head[M];

 int nxt[M],son[M],deep[N];

 int read(){

     int sum=;

     char ch=getchar();

     while (ch<''||ch>'')

         ch=getchar();

     while (ch>=''&&ch<=''){

         sum=sum*+ch-'';

         ch=getchar();

     }

     return sum;

 }

 void uni(int x,int y){

     size++;

     nxt[size]=head[x];

     head[x]=size;

     son[size]=y;

 }

 void swap(int &a,int &b){

     int tmp=a;

     a=b;

     b=tmp;

 }

 void dfs(int fa,int x){

     for (int k=head[x];k;k=nxt[k]){

         int y=son[k];

         if (y==fa)

             continue;

         father[y][]=x;

         deep[y]=deep[x]+;

         dfs(x,y);

     }

 }

 void pre(){

     for (int j=;j<=p;j++)

         for (int i=;i<=n;i++)

             father[i][j]=father[father[i][j-]][j-];

 }

 int LCA(int x,int y){

     if (deep[x]<deep[y])

         swap(x,y);

     int d=deep[x]-deep[y];

     for (int j=p;j>=;j--)

         if (d&(<<j))

             x=father[x][j];

     if (x==y)

         return x;

     for (int j=p;j>=;j--)

         if (father[x][j]!=father[y][j]){

             x=father[x][j];

             y=father[y][j];

         }

     return father[x][];

 }

 int check(int x,int y){

     for (int j=p;j>=;j--)

         if (deep[father[x][j]]>=deep[y])

             x=father[x][j];

     if (x==y)

         return ;

     return ;

 }//deep[x]>deep[y]

 int main(){

     int u,v;

     size=;

     n=read();

     q=read();

     for (int i=;i<n;i++){

         u=read();

         v=read();

         uni(u,v);

         uni(v,u);

     }

     deep[]=;

     father[][]=;

     dfs(,);

     pre();

     int a,b,c,d;

     for (int i=;i<=q;i++){

         a=read();

         b=read();

         c=read();

         d=read();

         int lcax=LCA(a,b);

         int lcay=LCA(c,d);

         if (deep[lcax]<deep[lcay]){

             swap(lcax,lcay);

             swap(a,c);

             swap(b,d);

         }//deep[lcax]>deep[lcay]

         if (check(lcax,lcay)&&(check(c,lcax)||check(d,lcax)))

             printf("Y\n");

         else

             printf("N\n");

     }

     return ;

 }

最后想说…………LCA的pre（）函数……j 如果打错从0循环的话会很GG……

因为它会WA……不一定是RE……

巴特西

【洛谷P3398】仓鼠找sugar

最新文章

热门文章