题解 P3398 【仓鼠找sugar】

· · 题解

询问树上a到b，c到d的两条路径是否相交
我们容易发现，如果相交，记 x=lca(a,b)，y=lca(c,d)，则必有x在c~d路径上或y在a~b路径上
之前类似的题解都没有给出证明。为什么呢？
首先易知两点的lca在其路径上。如果路径相交，那么x要么在相交的路径上，要么不在。我们不妨记相交的那段为e~f
如果不在，由对称性，不妨设x靠近a，那么有a到x深度递减，b到e、e到f、f到x深度递减；同样，肯定有c到f、d到e深度递减，由此可知，y必定为f，由此得证（以上的e、f和c、d的相对位置是由对称性直接设的，我表达不太好，各位不妨画图理解一下qwq）
如果在的话就更好证了，各位不妨试试qwq
那么如何查看一个点是否在一条路径上呢？我找了一个性质，即须满足该点到路径两端点的距离和等于两端点的距离，距离用lca和深度就可以了
代码如下，用倍增做的：

#include <cstdio>
#define DEBUG printf("Passing [%s] in LINE %d.\n", __FUNCTION__, __LINE__);
#define MAXN 100005
using namespace std;

struct edge {
    int v, pre;
} e[MAXN<<1];
int N, T, fst[MAXN], dep[MAXN], dp[MAXN][18];
int vis[MAXN], lg[MAXN];

inline int read()
{
    register int o = 0;
    register char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >='0' && c <='9') o = (o<<3)+(o<<1)+(c&15), c = getchar();
    return o;
}
inline int abs(int x) { return x > 0 ? x : -x; }
inline int swap(int &x, int &y) { x ^= y ^= x ^= y; }
inline int addedge(int a, int b, int k)
{
    e[k] = (edge){b, fst[a]}, fst[a] = k;
}
int build(int k, int d)
{
    vis[k] = 1, dep[k] = d;
    for (register int o=fst[k]; o; o=e[o].pre)
        if (!vis[e[o].v]) dp[e[o].v][0] = k, build(e[o].v, d+1);
}
int prepare(int k)
{
    vis[k] = 0;
    for (register int i=1; i<=lg[dep[k]]; i++)
        dp[k][i] = dp[dp[k][i-1]][i-1];
    for (register int o=fst[k]; o; o=e[o].pre)
        if (vis[e[o].v]) prepare(e[o].v);
}
int init()
{
    N = read(), T = read();
    for (register int i=1, a, b, c; i<N; i++) {
        a = read(), b = read();
        addedge(a, b, i);
        addedge(b, a, i+N);
    }
    build(1, 0);
    for (register int i=1; i<=N; i++)
        lg[i] = lg[i-1] + ((1<<(lg[i-1]+1)) == i);
    prepare(1);
}
int lca(int a, int b)
{
    if (dep[a] < dep[b]) swap(a, b);
    while (dep[a] > dep[b]) a = dp[a][lg[dep[a]-dep[b]]];
    if (a == b) return a;
    for (register int i=lg[dep[a]]; i>=0; i--) 
        if (dp[a][i] != dp[b][i]) a = dp[a][i], b = dp[b][i];
    return dp[a][0];
}
inline int dis(int a, int b)
{
    register int c = lca(a, b);
    return abs(dep[c]-dep[a]) + abs(dep[c]-dep[b]); 
}
int work()
{
    for (register int a, b, c, d, x, y; T; T--)
    {
        a = read(), b = read(), c = read(), d = read();
        x = lca(a, b), y = lca(c, d);
        if (dis(a, y)+dis(b, y)==dis(a, b) || dis(c, x)+dis(d, x)==dis(c, d)) puts("Y");
        else puts("N");
    }
}
int main()
{
    init();
    work(); 
}