算法分析

考虑朴素的算法
t1 = lca(x1,y1), S1 = x1->t1 ∪ t1->y1;
同理可得t2和S2。判断S1∩S2是否为空

假设有交点t且假设经过y1,y2，所以x1->t1->t->y1,x2->t2->t->y2,因为t只有一个父亲，所以t1,t2一定是祖先关系，那么t1或t2一定是交点，假设t1是交点，即t2是t1的祖先，则需要两个判定条件：

lca(t1,t2) = t2
lca(t1,y2) = t1 或 lca(t1,x2) = t1

程序代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100050;
struct nod{
    int to, cost;
    nod(int a=0,int b=0){to = a; cost = b;}
};
int dep[maxn], se[maxn*2], no[maxn*2], fir[maxn], st[maxn*2][20], lo[200005];
vector<nod> g[maxn];
int n, m;
int cnt, sum;
int T;
void Init(){
    for(int i = 0; i <= n; i++)
        {
            g[i].clear();
            dep[i] = 0;
        }
    sum = cnt = 0;
}
void mkst(){
    for(int i = 0; i <= cnt; i++) st[i][0] = se[i];
    for(int j = 1; (1<<j) <= cnt; j++)
        for(int i = 1; i <= cnt-(1<<j)+1; i++)
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}

void dfs(int u, int f, int di){
    dep[u] = di;
    no[++sum] = u;
    int t = sum;
    se[++cnt] = t;
    fir[u] = cnt;
    for(int i = 0; i < g[u].size(); i++)
    {
        if(g[u][i].to == f) continue;
        dfs(g[u][i].to, u, di+g[u][i].cost);
        se[++cnt] = t;
    }
}
int find(int p, int q){
    if(p > q) swap(p, q);
    int j = lo[q-p+1];
    return min(st[p][j],st[q-(1<<j)+1][j]);
}
/*int cal(int x, int y){
    int now = no[find(fir[x], fir[y])];
    return dep[x] + dep[y] -2*dep[now];
}*/
int lca(int a, int b){
    return no[find(fir[a], fir[b])];
}
int main(){
    lo[1] = 0;
    for(int i = 2; i <= 200000; i++) lo[i] = lo[i>>1]+1;
    scanf("%d", &T);
    while(T--){
        Init();
        scanf("%d%d",&n, &m);
        for(int i = 0; i < n-1; i++){
            int u, v;
            scanf("%d%d",&u, &v);
            g[u].push_back({v,1});
            g[v].push_back({u,1});
        }
        dfs(1,0,0);mkst();
        while(m--){
            int x1,x2,y1,y2;
            bool fg = false;
            scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
            int t1 = lca(x1,y1);
            int t2 = lca(x2,y2);
            if(lca(t1,t2) == t1){
                if(lca(t2,x1) == t2 || lca(t2,y1) == t2)
                    fg = true;
            }
            if(lca(t1,t2) == t2){
                if(lca(t1,x2) == t1 || lca(t1,y2) == t1)
                    fg = true;
            }
            printf("%s\n", (fg == true ?"YES" : "NO")); 
        }
    }
    return 0;
}