题解 P3398 【仓鼠找sugar】

· · 题解

其实，多画几个图模拟一下，可以发现如下一个神奇的规律：

如果两条路径相交，那么一定有一条路径的LCA在另一条路径上

而判断一个节点x，是否在路径s-t上需要满足如下几个条件

    - deep[x]>=deep[LCA(s,t)]

    - LCA(s,x)=x或LCA(t,x)=x;

所以分两种情况讨论一下即可

时间复杂度O(n log n)

下面是树剖LCA的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 100000+15 
using namespace std;
vector<int>vec[MAXN];
int n,q,v,u,a,b,c,d;
int deep[MAXN],dad[MAXN],size[MAXN],top[MAXN];
int dfs(int x){
    size[x]=1;
    deep[x]=deep[dad[x]]+1;
    for(int i=0;i<vec[x].size();i++)
        if(dad[x]!=vec[x][i]){
            dad[vec[x][i]]=x;
            dfs(vec[x][i]);
            size[x]+=size[vec[x][i]]; 
        } 
} 
int dfs1(int x){
    int t=0;
    if(!top[x])    top[x]=x;
    for(int i=0;i<vec[x].size();i++)
        if(dad[x]!=vec[x][i]&&size[vec[x][i]]>size[t])
            t=vec[x][i];
    if(t){
        top[t]=top[x];
        dfs1(t);
    }    
    for(int i=0;i<vec[x].size();i++)
        if(dad[x]!=vec[x][i]&&vec[x][i]!=t)
            dfs1(vec[x][i]);
}
int LCA(int x,int y){
    for(;top[x]!=top[y];){
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        x=dad[top[x]];
    }
    if(deep[x]>deep[y])    swap(x,y);
    return x;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1);
    dfs1(1);
    for(int i=1;i<=q;i++){
        cin>>a>>b>>c>>d;
        int S=LCA(a,b);
        int T=LCA(c,d);
        if(deep[S]<deep[T]){
            swap(S,T);
            swap(a,c);
            swap(b,d);
        }    
        if(LCA(S,c)==S||LCA(S,d)==S)    cout<<"Y"<<endl;
        else    cout<<"N"<<endl;
    }
}