P3398 仓鼠找 sugar

SunnyYuan的博客 / 2024-08-09 / 原文

题意

判断树上两条路径是否相交。

思路

可以根据距离进行判断。

如果 $dis(u, v) = dis(lca(g, t), u) + dis(lca(g, t), v)$，说明 $g$ 和 $t$ 的 $lca$ 在 $u$ 到 $v$ 的路径上，两条路径相交。

如果 $dis(g, t) = dis(lca(u, v), g) + dis(lca(u, v), t)$，说明 $u$ 和 $v$ 的 $lca$ 在 $u$ 到 $v$ 的路径上，两条路径相交。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct edge {
    int to, next;
} e[N * 2];

int head[N], idx = 1;

void add(int u, int v) {
    idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx;
}

int fa[20][N], dep[N];
int n, q;

void dfs(int u, int f) {
    fa[0][u] = f;
    dep[u] = dep[f] + 1;
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == f) continue;
        dfs(to, u);
    }
}

void initf() {
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[j][i] = fa[j - 1][fa[j - 1][i]];
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    for (int i = 19; i >= 0; i--) {
        if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
    }

    if (u == v) return u;

    for (int i = 19; i >= 0; i--) {
        if (fa[i][u]!= fa[i][v]) u = fa[i][u], v = fa[i][v];
    }
    return fa[0][u];
}

int dis(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }

    dfs(1, 0);
    initf();

    while (q--) {
        int u, v, g, t;
        cin >> u >> v >> g >> t;
        if (dis(u, v) == dis(lca(g, t), u) + dis(lca(g, t), v)) cout << "Y\n";
        else if (dis(g, t) == dis(lca(u, v), g) + dis(lca(u, v), t)) cout << "Y\n";
        else cout << "N\n";
    }
    return 0;
}