跳转至

Passable Paths (CF 1702)

原题链接

题意

一颗由 \(n\) 个顶点，\(n - 1\) 条边组成的树，判断能否一条路走完给出的 \(k\) 个顶点。

思路

先预处理出所有点在树中的深度，记为 \(d[i]\)，对于每一次询问，首先根据深度从大到小进行排序，如果两个点是在一条链上的话，那么这两个点中，有一个点必为两个点的 \(LCA\)。因此可以先求出最大深度点中，同在一条链上的所有点，并且标记它。对于另外一个方向上的点（可能为0），找到未被标记且深度最大的点，重复上次操作。如果所有点都被标记且两个下降点不相交或者他们的lca的深度不大于最浅的点，那么答案就是 YES，否则为 NO。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

const int N = 200010, M = 400010;

int n;
int h[N], e[M], ne[M], idx;
int fa[N][20], d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int root) {
    memset(d, 0x3f, sizeof d);
    d[0] = 0;
    d[root] = 1;

    queue<int> q;
    q.push(root);

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[u] + 1) {
                d[j] = d[u] + 1;
                q.push(j);
                fa[j][0] = u;
                for (int k = 1; k < 20; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    if (d[a] < d[b]) swap(a, b);

    for (int k = 19; k >= 0; k--)
        if (d[fa[a][k]] >= d[b])
            a = fa[a][k];

    for (int k = 19; k >= 0; k--)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }

    return a == b ? a : fa[a][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    bfs(1);

    int q;
    cin >> q;
    while (q--) {
        int m;
        cin >> m;
        vector<int> p(m);
        for (int &x : p) cin >> x;
        sort(p.begin(), p.end(), [](int a, int b) {
            return d[a] > d[b];
        });

        vector<bool> st(m);
        for (int i = 0; i < m; i++)
            if (lca(p[0], p[i]) == p[i])
                st[i] = true;

        int k = 0;
        while (k < m && st[k]) k++;

        if (k == m) {
            cout << "YES" << endl;
            continue;
        }

        for (int i = k; i < m; i++)
            if (lca(p[k], p[i]) == p[i])
                st[i] = true;

        bool ok = true;
        for (auto x : st) ok &= x;
        ok &= d[lca(p[0], p[k])] <= d[p.back()];

        cout << (ok ? "YES" : "NO") << endl;
    }

    return 0;
}
回到页面顶部