hihocoder[Offer收割]编程练习赛19 D 相交的铁路线（树上路径交）

　　傻逼题… 裸的树上路径交

　　两条树上的路径$[a,b]$和$[c,d]$有交，则有$lca(a,b)$在$[c,d]$上或$lca(c,d)$在$[a,b]$上。

　　其实只要深度大的$lca$在另一条链上就好了，所以设$x=lca(a,b)$深度较大。

　　充分性证明：$x$在$[c,d]$上，则$[a,b]$和$[c,d]$显然有交。

　　必要性证明：$x$不在$[c,d]$上，如果$[a,b]$上有点$y$与$[c,d]$有交，因为$lca(c,d)$深度较小，所以$y$的深度必定小于$x$，那么$x$就不是$lca(a,b)$了，矛盾，所以如果$x$不在$[c,d]$上，$[a,b]$与$[c,d]$无交。

　　证毕。

　　其实根本不用证明…太容易理解了…

　　判断$x$在$[c,d]$上只需要判断$x$是$lca(c,d)$的儿子且$x$是$c$或$d$的父亲。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=;
struct poi{int too, pre;}e[maxn<<];
int T, n, q, x, y, x2, y2, tot, tott;
int top[maxn], last[maxn], dep[maxn], l[maxn], r[maxn], size[maxn], son[maxn], fa[maxn];
inline void read(int &k)
{
    int f=; k=; char c=getchar();
    while(c<'' || c>'') c=='-' && (f=-), c=getchar();
    while(c<='' && c>='') k=k*+c-'', c=getchar();
    k*=f;
}
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
void dfs1(int x)
{
    l[x]=++tott; size[x]=;
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa[x])
    {
        dep[too]=dep[x]+; fa[too]=x;
        dfs1(too); size[x]+=size[too];
        if(size[too]>size[son[x]]) son[x]=too;
    }    r[x]=tott;
}
void dfs2(int x, int tp)
{
    top[x]=tp;
    if(son[x]) dfs2(son[x], tp);
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa[x] && too!=son[x]) dfs2(too, too);
}
inline int lca(int x, int y)
{
    int f1=top[x], f2=top[y];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2]) swap(x, y), swap(f1, f2);
        x=fa[f1]; f1=top[x];
    }
    if(dep[x]<dep[y]) swap(x, y);
    return y;
}
bool check(int x, int y, int ls, int rs)
{
    if(l[x]<l[y] || r[y]<l[x]) return ;
    if(l[x]<=l[ls] && l[ls]<=r[x]) return ;
    if(l[x]<=l[rs] && l[rs]<=r[x]) return ;
    return ;
}
int main()
{
    read(T);
    while(T--)
    {
        memset(last, , sizeof(last)); tot=tott=;
        read(n); read(q);
        for(int i=;i<n;i++) read(x), read(y), add(x, y), add(y, x);
        dfs1(); dfs2(, );
        for(int i=;i<=q;i++)
        {
            read(x); read(y); read(x2); read(y2);
            int f1=lca(x, y), f2=lca(x2, y2);
            if(dep[f1]<dep[f2]) swap(f1, f2), swap(x, x2), swap(y, y2);
            printf("%s\n", check(f1, f2, x2, y2)?"YES":"NO");
        }
    }
}