洛谷P3398 倉鼠找sugar

LCA

題目傳送門

其實就是讓你判斷樹上的兩條路徑是否相交。

對于兩條相交的路徑，有這樣一條性質：

一條路徑的LCA必然與另一條路徑相交

而一個點與一條路徑相交需滿足以下性質：

①：該節點的深度≥路徑兩端點LCA的深度

②：該節點與路徑至少一個端點的LCA為他自己

于是不停跑LCA就行啦！

感覺Tarjan有點難搞，就寫了ST

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100000
using namespace std;
struct edge{
    int next,to;
};
int n,q,k;
int h[MAXN+],fa[MAXN+][],depth[MAXN+];
edge ed[MAXN*+];
inline char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
inline int _read(){
    int num=; char ch=readc();
    while (ch<'0'||ch>'9') ch=readc();
    while (ch>='0'&&ch<='9') { num=num*+ch-; ch=readc(); }
    return num;
}
void dfs(int x,int dep){
    depth[x]=dep;
    for (int i=h[x];i;i=ed[i].next)
        if (ed[i].to!=fa[x][]){
            fa[ed[i].to][]=x;
            dfs(ed[i].to,dep+);
        }
}
void make(){
    for (int j=;j<=;j++)
        for (int i=;i<=n;i++)
            fa[i][j]=fa[fa[i][j-]][j-];
}
int lca(int x,int y){
    if (depth[x]<depth[y]) swap(x,y);
    for (int i=;i>=;i--)
        if (depth[fa[x][i]]>=depth[y]) x=fa[x][i];
    if (x==y) return x;
    for (int i=;i>=;i--)
        if (fa[x][i]!=fa[y][i]){
            x=fa[x][i]; y=fa[y][i];
        }
    return fa[x][];
}
bool LCA(int u,int v,int x,int y){
    int t1=lca(u,v),t2=lca(x,y);
    if ((depth[t1]>=depth[t2]&&(lca(t1,x)==t1||lca(t1,y)==t1))||(depth[t1]<=depth[t2]&&(lca(t2,u)==t2||lca(t2,v)==t2)))
        return true;
    return false;
}
void addedge(int x,int y){
    ed[++k].next=h[x]; ed[k].to=y; h[x]=k;
}
int main(){
    n=_read(); q=_read();
    for (int i=;i<n;i++){
        int u=_read(),v=_read();
        addedge(u,v); addedge(v,u);
    }
    fa[][]=;
    dfs(,);
    make();
    for (int i=;i<=q;i++){
        int u=_read(),v=_read(),x=_read(),y=_read();
        if (LCA(u,v,x,y)) printf("Y\n"); else printf("N\n");
    }
    return ;
}