Logu p3398 hamsters find sugar solution

Luogu P3398 Hamsters look for sugar Answer key

Topic link ：P3398 Hamsters look for sugar

The question ：

Hamster's and his base （mei） friend （zi）sugar Living in underground caves , The number of each node is 1~n. The underground cave is a tree structure . On this day, hamster plans to go from his bedroom （a） To the restaurant （b）, And his base friend is going to be in his bedroom at the same time （c） To the library （d）. They all take the shortest path . Now little hamster wants to know , Is it possible to be somewhere , You can meet his friends ？

Hamsters are so weak , And every day zzq Uncle abuse , Please come and save him ！

$n\le 10^5,q\le 10^5$

Simplify the meaning of the question , It is to judge whether there is intersection given the path on two trees

set up $a,b$ Of LCA by $x$ ,$c,d$ Of LCA by $y$

It is not difficult to find that if two trees intersect , That must meet the following requirements At least one condition

• $x$ stay $c,d$ On the way
• $y$ stay $a,b$ On the way

Consider how to determine whether it is on the path

It's very simple , as long as $x$ To $c,d$ The sum of distances equals $c$ To $d$ Distance of , be $x$ It's just $c,d$ On the way

Empathy , as long as $y$ To $a,b$ The sum of distances equals $a$ To $b$ Distance of , be $y$ It's just $a,b$ On the way

Then write a multiplier LCA It's over

Time complexity $O(m\log n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,Q,pos=1,head[N],dep[N],lg[N],fa[N][20];
struct Edge{
    int u,v,next;}e[N<<1];
void addEdge(int u,int v)
{
    
    e[++pos]={
    u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    
    fa[u][0]=f;
    dep[u]=dep[f]+1;
    for(int i=1; i<=lg[dep[u]]; i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v!=f)dfs(e[i].v,u);
}
int lca(int x,int y)
{
    
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int i=lg[dep[x]]; i>=0; i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int dis(int x,int y)
{
    
    int d=lca(x,y);
    return abs(dep[x]-dep[d])+abs(dep[y]-dep[d]);
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i=1,u,v; i<n; i++)
    {
    
        cin >> u >> v;
        addEdge(u,v);addEdge(v,u);
    }
    for(int i=1; i<=n; i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(1,1);
    for(int a,b,c,d; Q--;)
    {
    
        cin >> a >> b >> c >> d;
        int d1=lca(a,b),d2=lca(c,d);
        if(dis(a,d2)+dis(d2,b)==dis(a,b)||dis(c,d1)+dis(d1,d)==dis(c,d))
            cout << "Y\n";
        else cout << "N\n";
    }
    return 0;
}