P3398 仓鼠找sugar lca

短命女 2021-12-13 13:03 192阅读 0赞

## 题目描述 ##

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

## 输入输出格式 ##

输入格式：

第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

输出格式：

对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

## 输入输出样例 ##

输入样例\#1：  复制

5 5
    2 5
    4 2
    1 3
    1 4
    5 1 5 1
    2 2 1 4
    4 1 3 4
    3 1 1 5
    3 5 1 4

输出样例\#1：  复制

Y
    N
    Y
    Y
    Y
    
    求树上路径是否相交
    询问树上a到b，c到d的两条路径是否相交 我们容易发现，如果相交，记 x=lca(a,b)，y=lca(c,d)，则必有x在c~d路径上或y在a~b路径上

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    //input by bxd
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define repp(i,a,b) for(int i=(a);i>=(b);--i)
    #define RI(n) scanf("%d",&(n))
    #define RII(n,m) scanf("%d%d",&n,&m)
    #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
    #define RS(s) scanf("%s",s);
    #define ll long long
    #define pb push_back
    #define REP(i,N)  for(int i=0;i<(N);i++)
    #define CLR(A,v)  memset(A,v,sizeof A)
    //
    #define inf 0x3f3f3f3f
    const int N=500000+5;
    const int M=2*500000+5;
    struct Edge
    {
        int nex,v,to;
    }edge[M];
    int lg[N],head[M],pos;
    void init(int n)//常数优化
    {
        pos=0;
        CLR(head,0);
        for(int i=1;i<=n;i++)
            lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    void add(int a,int b)
    {
        edge[++pos].nex=head[a];
        head[a]=pos;
        edge[pos].to=b;
    }
    int fa[N][100];
    int deth[N];
    void dfs(int cur,int fath)
    {
        deth[cur]=deth[fath]+1;
        fa[cur][0]=fath;
        for(int i=1;(1<<i)<=deth[cur];i++)
        fa[cur][i]=fa[ fa[cur][i-1] ][i-1];
    
        for(int i=head[cur];i;i=edge[i].nex)
        if(edge[i].to!=fath)
            dfs(edge[i].to,cur);
    }
    int lca(int x,int y)
    {
        if(deth[x]<deth[y])
        swap(x,y);
        while(deth[x]>deth[y])
        x=fa[x][ lg[ deth[x]-deth[y] ]-1];
        if(x==y)return x;
        for(int k=lg[deth[x]]-1;k>=0;k--)
        if(fa[x][k]!=fa[y][k])
        x=fa[x][k],y=fa[y][k];
        return fa[x][0];
    }
    int n,m,q,a,b,c,d;
    int dis(int a,int b)
    {
        int c=lca(a,b);
        return abs(deth[c]-deth[a])+abs(deth[c]-deth[b]);
    }
    int main()
    {
        RII(n,m);
        init(n);
        rep(i,1,n-1)
        {
            RII(a,b);add(a,b);add(b,a);
        }
        dfs(1,0);
        rep(i,1,m)
        {
            RII(a,b);RII(c,d);
            int x=lca(a,b),y=lca(c,d);
            if(dis(a,y)+dis(b,y)==dis(a,b)||dis(c,d)==dis(c,x)+dis(d,x))
                puts("Y");
            else puts("N");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/bxd123/p/11003416.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/7b621ee62ded40a7bbb9068902680c2d.png