仓鼠找sugar

你的名字 2021-11-04 21:56 253阅读 0赞

\[Time Gate\]

https://www.luogu.org/problemnew/show/P3398

【解题思路】

随便画一棵树，然后会发现，两条路径有公共部分的话，必定有一条路径（的两个端点）的LCA在另一条路径上

这样我们只要判断一个节点是否在一条路径上即可

然后联想到绝对值的几何意义（反正我是这么想到的...）满足以下规律的才有可能满足节点lca在路径a-b上

dis(lca,a)+dis(lca,b)==dis(a,b)dis(lca,a)+dis(lca,b)==dis(a,b)dis(lca,a)\+dis(lca,b)==dis(a,b)

注意:要判断两次，因为有可能是LCA(a,b)在c-d上，也有可能是LCA(c,d)在a-b上

然后我打的树剖LCA，看着不爽的可以换成自己LCA啦

【code】

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #define writeln(x)  write(x),puts("")
     5 #define writep(x)   write(x),putchar(' ')
     6 using namespace std;
     7 inline int read(){
     8     int ans=0,f=1;char chr=getchar();
     9     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
    10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    11     return ans*f;
    12 }void write(int x){
    13     if(x<0) putchar('-'),x=-x;
    14     if(x>9) write(x/10);
    15     putchar(x%10+'0');
    16 }const int M = 1e5+5;
    17 int head[M],ver[M<<1],nxt[M<<1],tot,n,m,idx[M],fa[M],son[M],sz[M],tp[M],dep[M];
    18 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
    19 void dfs1(int x,int f){
    20     fa[x]=f,dep[x]=dep[f]+1;sz[x]=1;
    21     for(int i=head[x];i;i=nxt[i]){
    22         if(ver[i]==f) continue;
    23         dfs1(ver[i],x);
    24         sz[x]+=sz[ver[i]];
    25         if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
    26     }
    27 }int t;
    28 void dfs2(int x,int topf){
    29     tp[x]=topf,idx[x]=++t;
    30     if(!son[x]) return;
    31     dfs2(son[x],topf);
    32     for(int i=head[x];i;i=nxt[i])
    33         if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
    34 }
    35 int LCA(int x,int y){
    36     while(tp[x]!=tp[y]){
    37         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
    38         x=fa[tp[x]];
    39     }if(dep[x]>dep[y]) swap(x,y);
    40     return x;
    41 }
    42 int DIS(int x,int y){
        return dep[x]+dep[y]-2*dep[LCA(x,y)];}
    43 inline bool check(int a,int b,int c,int d){
    44     int x=LCA(a,b);
    45     if(DIS(x,c)+DIS(x,d)==DIS(c,d)) return 1;
    46     return 0;
    47 }
    48 int main(){
    49     n=read(),m=read();
    50     for(int i=1,x,y;i<n;i++){
    51         x=read(),y=read();
    52         add(x,y),add(y,x);
    53     }dfs1(1,0),dfs2(1,1);
    54     while(m--){
    55         int a=read(),b=read(),c=read(),d=read();
    56         if(check(a,b,c,d)||check(c,d,a,b)) puts("Y");
    57         else puts("N");
    58     }
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/66dzb/p/11163111.html