相交（inter）

【分析】

考场上只是简单的打了暴力，连链的特殊情况也没考虑，O(n^2)算法只是可怜兮兮的骗了30分。。。。

注意这道题的题解并不难，如果见过类似的模型，只要上次不是抄了题解草草了事就一定能获得满分，但要有类似的思路来想到此题，并不容易。 请仔细观察学习此类算法，以便考场之上可以骗分更多。

30分的暴力很直接，每次将树上的一条链打上标记，再在另一条链中遍历是否有点被打上标记。

优化的思路是，既然我们不能优化访问的次数，能否加快每次判断的速度。将问题抽象出来，是给定两条链的首尾位置，询问树上的两条链是否有交集。然后就是焦头烂额，昏天黑地的胡思乱想。这里直接上结论如果两条链在树上有交集，则一条链的LCA一定在另一条链上。（注意两链不分先后）（为什么？）
充分性：因为LCA同时在两条链上，所以两条链一定相交（香蕉？雾）
必要性：把树向下放置看，如下图：

可以看到，两点的lca是他们向上，较少的分差点的中的一个。感性理解一下，两条链就像是垂了下来的两条列。若LCA深度较大的链，LCA不在另一条链上，那肯定就不相交了（逃）

由于懒得判断两点LCA的深度，我们可以利用如下判断:

bool inlian(int a,int b,int c){
    return lca(a,c)==c&&d[c]>=d[b];
}
bool check(int A,int B,int C,int D){
    int l1=lca(A,B),l2=lca(C,D);
    return (inlian(A,l1,l2)||inlian(B,l1,l2)||inlian(C,l2,l1)||inlian(D,l2,l1));
}

下放代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=100100;

struct Edge{
    int v,nxt;
}e[maxn*2];
int p[maxn][20],dep[maxn],sta[maxn],tot,n,u,v,x,y;

void addedge(int u,int v)
{
    e[++tot].v=v;
    e[tot].nxt=sta[u];
    sta[u]=tot;
}

int read(){
    int re=0,f=1;char c=getchar();
    while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();}
    while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();}
    return re*f;
}

void dfs(int u,int f,int d){
    p[u][0]=f;
    dep[u]=d;
    for(int i=1;i<=18;++i)
        p[u][i]=p[p[u][i-1]][i-1];
    for(int ed=sta[u];ed;ed=e[ed].nxt)
        if(e[ed].v!=f)
            dfs(e[ed].v,u,d+1);
}

int lca(int u,int v){
    for(int i=18;i>=0;--i)
        if(dep[p[u][i]]>=dep[v])
            u=p[u][i];
    for(int i=18;i>=0;--i)
        if(dep[p[v][i]]>=dep[u])
            v=p[v][i];
    if(u==v) return u;
    for(int i=18;i>=0;--i) if(p[u][i]!=p[v][i]) {u=p[u][i];v=p[v][i];}
    return p[u][0];
}

bool inlian(int u,int v,int w){
    return (lca(u,w)==w)&&(dep[w]>=dep[v]);
}

bool pd(int a,int b,int c,int d){
    int l1=lca(a,b),l2=lca(c,d);
    return (inlian(a,l1,l2))||(inlian(b,l1,l2))||(inlian(c,l2,l1))||(inlian(d,l2,l1)); 
}

int main(){
    n=read();memset(p,0,sizeof(p));tot=1;
    for (int i=1;i<n;++i) {u=read();v=read();addedge(u,v);addedge(v,u);}
    dfs(1,0,1);
    for (int q=read();q;--q){
        u=read();v=read();x=read();y=read();
        if (pd(u,v,x,y)) cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;
}

转载自：https://blog.csdn.net/xyc1719/article/details/81514977