【简单图论】CF898 div4 H

爱被打了一巴掌 2024-03-01 01:46 79阅读 0赞

[Problem - H - Codeforces][]

题意：

![4b37a99e5b464ba681c364f7b47a7a52.png][]

思路：

手玩一下样例就能发现简单结论：

v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES

否则就是NO

实现就很简单，先去树上找环，然后找出这个根，分别给a 和 b BFS一遍，得出两个dis数组，比较一下即可

对于只有的环情况 和 m = v 的情况需要特判

Code：

#include <bits/stdc++.h>
    
    constexpr int N = 2e5 + 10;
    constexpr int M = 1e6 + 10;
    constexpr int Inf = 1e9;
    
    std::queue<int> q1, q2;
    std::vector<int> adj[N];
    
    int n, a, b;
    int top = 0;
    int u[N], v[N];
    int st[N], r[N];
    int dis1[N];
    int dis2[N];
    
    int find_r(int u, int fa) {
        if (st[u]) return u;
        st[u] = 1;
        for (auto v : adj[u]) {
            if (v == fa) continue;
            int t = find_r(v, u);
            if (t) {
                r[++ top] = u;
                st[u] = 2;
                return t == u ? 0 : t;
            }
        }
        return 0;
    }
    void bfs1(int u) {
        memset(dis1, 0x3f, sizeof(dis1));
        dis1[u]= 0;
        q1.push(u);
        while(!q1.empty()) {
            int u = q1.front();
            q1.pop();
            for (auto v : adj[u]) {
                if (dis1[v] > dis1[u] + 1) {
                    dis1[v] = dis1[u] + 1;
                    q1.push(v);
                }
            }
        }
    }
    void bfs2(int u) {
        memset(dis2, 0x3f, sizeof(dis2));
        dis2[u] = 0;
        q2.push(u);
        while(!q2.empty()) {
            int u = q2.front();
            q2.pop();
            for (auto v : adj[u]) {
                if (dis2[v] > dis2[u] + 1) {
                    dis2[v] = dis2[u] + 1;
                    q2.push(v);
                }
            }
        }
    }
    void solve() {
        std::cin >> n >> a >> b;
        top = 0;
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        for (int i = 1; i <= n; i ++) {
            st[i] = 0;
            adj[i].clear();
        }
        for (int i = 1; i <= n; i ++) {
            std::cin >> u[i] >> v[i];
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);
        }
        if (a == b) {
            std::cout << "NO" << "\n";
            return;
        }
        find_r(1, 0);
        bfs1(b);
        int miu1 = Inf, ansu = 0;
        for (int i = 1; i <= n; i ++) {
            if (st[i] == 2 && miu1 > dis1[i]) {
                miu1 = dis1[i];
                ansu = i;
            }
        }
        if (st[b] == 2) {
            std::cout << "YES" << "\n";
            return;
        }
        bfs2(a);
        int ans1 = dis2[ansu];
        int ans2 = miu1;
        if (ans1 > ans2) std::cout << "YES" << "\n";
        else std::cout << "NO" << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - H - Codeforces]: https://codeforces.com/contest/1873/problem/H
[4b37a99e5b464ba681c364f7b47a7a52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/640fd6dec77d4f56850364ed7e9f503a.png