自动搬运

查看原文

来自洛谷，原作者为

	zhyh 菜菜菜

搬运于2025-08-24 21:48:35，当前版本为作者最后更新于2018-09-08 21:21:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

询问树上$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(); 
}