仓鼠找sugar ------ LCA

这道题给我的 启示是一个规律：

树上有两条路径，两条路径的端点分别为(a,b)以及(c,d)

这两条路径相交，则LCA(a,b) 的祖先必然是LCA(c,d)或者是LCA(c,d)的祖先是LCA(a,b)，

int LA,LB;
      LA = LCA(a,b); LB = LCA(c,d);
      if(LCA(LA,LB) != LA && LCA(LA,LB) != LB){
      cout <<"N
" ;
      continue;
}

同时不妨假设depth[LCA(c,d)] > depth[LCA(a,b)],那么假如两条路径有交点,

　　depth[LCA(LCA(c,d),a)] >= depth[LCA(c,d)] || depth[LCA(LCA(a,b),b)] >= depth[LCA(c,d)]

即c，d的最近公共祖先与a或者b的公共祖先的深度大于等于c,d的最近公共祖先的深度

贴上代码:

#include <bits/stdc++.h>
using namespace std;
struct node{int u,v;}r[200005];
int n , m , q;
int depth[200005] = {0},vis[300005]={0},start[300005];
int parent[100005][21],Root;
int DFS(int x,int from){
    depth[x] = depth[from] + 1;
    vis[x] = 1;parent[x][0] = from;
    for(int i = 1 ; i <= 20 ; i ++)
        parent[x][i] = parent[parent[x][i-1]][i-1]; 
    for(int i = start[x] ; i <= m && r[i].u == x ; i ++){
        int to = r[i].v;
        if( !vis[to] )DFS(to , x);
    }
    return 0;
}
int cmp(node A,node B){return A.u < B.u;}
int LCA(int X,int Y){
    if( depth[X] > depth[Y] )swap(X,Y);
    for(int i = 20 ; i >= 0 ; i --)
        if(depth[parent[Y][i]] >= depth[X])
            Y = parent[Y][i];
    if( X == Y )return X;
    for(int i = 20 ; i >= 0 ; i --)
        if(parent[X][i] != parent[Y][i])
        X = parent[X][i] , Y = parent[Y][i];
    return parent[X][0];
}
int main(){
    cin >> n >> q;
    for(int i = 1 ; i <= n - 1; i ++){
        cin >> r[i].u >> r[i].v;
        r[i+n-1] = r[i];
        swap(r[i+n-1].u , r[i+n-1].v);
    }m = (n - 1)*2;
    sort(r + 1 , r + 1 + m , cmp);int ls = -1;
    for(int i = 1 ; i <= m ; i ++)
        if(ls != r[i].u)ls = r[i].u, start[ls] = i ;
    srand(time(NULL));
    Root = rand()%(n-1) + 1;
    DFS(Root,0);
    for(int i = 1 ; i <= q ; i ++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        int LA,LB;
        LA = LCA(a,b); LB = LCA(c,d);
        if(LCA(LA,LB) != LA && LCA(LA,LB) != LB){
            cout <<"N
" ;
            continue;
        }
        if(depth[LA] > depth[LB])swap(LA,LB),swap(a,c),swap(b,d);
        if(depth[LCA(LB,a)] < depth[LB] && depth[LCA(LB,b)] < depth[LB]){
            cout <<"N
" ;
            continue;
        }
        cout << "Y
";
    }
    return 0;
}