P3398 仓鼠找sugar 题解

RiceQuakes · 2023-12-13 09:19:05 · 个人记录

洛谷P3398 仓鼠找sugar 题解

题意：给定一棵树，共q次询问，每次询问给出a\ b\ c\ d四个点，判断a\ b与c\ d各自之间的简单路径是否存在重叠。

• 本题重点：树上路径重叠与点在路径上的判断

思路

简单思考易知：若路径重叠，则必有lca(a, b)在c\ d的路径上或lca(b,c)在a\ b的路径上。可将问题转化为判断lca是否在两点路径上。

设y=lca(c,d)，两点间路径长度为dis(a, b)，若dis(y, a) + dis(y, b) = dis(a, b)，则可判断y在a b的路径上。

代码

使用重链剖分求lca，代码很简单：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500000 + 10, INF = 9223372036854775807;
vector<int> con[N];
int dep[N], hson[N], fa[N], sz[N], top[N];
void dfs(int a, int f) {
    fa[a] = f;
    sz[a] = 1;
    dep[a] = dep[f] + 1;
    int mx = 0;
    for (auto t : con[a]) {
        if (t == f)
            continue;
        dfs(t, a);
        sz[a] += sz[t];
        if (sz[t] > mx) {
            mx = sz[t];
            hson[a] = t;
        }
    }
}
void df(int a) {
    for (auto t : con[a]) {
        if (t == fa[a])
            continue;
        if (t == hson[a])
            top[t] = top[a];
        else
            top[t] = t;
        df(t);
    }
}
int lca(int a, int b) {
    while (top[a] != top[b]) {
        if (dep[top[a]] > dep[top[b]])
            a = fa[top[a]];
        else
            b = fa[top[b]];
    }
    if (dep[a] > dep[b])
        return b;
    else
        return a;
}
int dis(int a, int b) {
    return dep[a] - dep[lca(a, b)] + dep[b] - dep[lca(a, b)];
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int f, t;
        cin >> f >> t;
        con[f].push_back(t);
        con[t].push_back(f);
    }
    dfs(1, 1);
    top[1] = 1;
    df(1);
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int x = lca(a, b), y = lca(c, d);
        if (dis(y, a) + dis(y, b) == dis(a, b) or
            dis(x, c) + dis(x, d) == dis(c, d)) {
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
    }
}