洛谷 P3398 仓鼠找sugar

传送门

题目分析：

就是给你两条路径的起点和终点，然后让你查找这两条路径有没有交点
if（有）puts("Y");
else puts("N");

解题思路：

很明显，是让我们求lca，我们先求出A与B的lca和C与D的lca，
然后我们在{A,C}{A,D}{B,C}{B,D}的lca的深度中找一个最大的，
然后与上述两个lca的深度比较，然后如果深度的最大值比两个lca的深度大的话，
那么就输出“Y”，然后不满足上边的情况那就输出“N”.

code

#include <bits/stdc++.h>
#define N 500010
#define M 1010

using namespace std;
int n, m, head[N], fa[N][21], deep[N];
int add_edge; bool vis[N];
struct node {
    int next, to;
}edge[N << 1];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void add(int from, int to) {
    edge[++add_edge].next = head[from];
    edge[add_edge].to = to;
    head[from] = add_edge;
}

void dfs(int x, int fath) {
    deep[x] = deep[fath] + 1;
    fa[x][0] = fath;
    for (int i = 1; i <= 20; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = edge[i].next) 
        if (edge[i].to != fath) dfs(edge[i].to, x);
}

int lca(int x, int y) {
    if (deep[x] > deep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (deep[fa[y][i]] >= deep[x])
            y = fa[y][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int main() {
    n = read(), m = read();
    for (int i = 1, x, y; i <= n - 1; i++) {
        x = read(), y = read();
        add(x, y), add(y, x);
    }
    dfs(1, 0);
    for (int i = 1, a, b, c, d; i <= m; i++) {
        a = read(), b = read(), c = read(), d = read();
        int lab = lca(a, b), lcd = lca(c, d);
        int mx = max(deep[lca(a, c)], max(deep[lca(a, d)], max(deep[lca(b, c)], deep[lca(b, d)])));
        if (mx >= deep[lab] && mx >= deep[lcd]) puts("Y");
        else puts("N");
    }
    return 0;
}

洛谷 P3398 仓鼠找sugar

原文：https://www.cnblogs.com/zzz-hhh/p/11668406.html