제출 #1359142

#제출 시각아이디문제언어결과실행 시간메모리
1359142NHristovNetwork (NOI23_network)C++20
100 / 100
185 ms55900 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

using namespace std;

const int N = 2e5 + 5, LG = 20;

int n, m;

struct fenwick {
    int bit[N];
    void upd(int pos, int val) {
        while (pos <= n) {
            bit[pos] += val;
            pos += pos & -pos;
        }
    }
    int sum(int pos) {
        int ret = 0;
        while (pos >= 1) {
            ret += bit[pos];
            pos -= pos & -pos;
        }
        return ret;
    }
    void upd_range(int l, int r, int val) {
        if (l > r) return;
        upd(l, val);
        if (r + 1 <= n) upd(r + 1, -val);
    }
} fen;

vector<array<int, 3>> byDep[N];
vector<int> g[N];
int dep[N], tin[N], tout[N], tim, up[LG][N];
bool mark[N];

void dfs(int u, int p) {
    tin[u] = ++tim;
    up[0][u] = p;
    for (int i = 1; i < LG; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (int v : g[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
    tout[u] = tim;
}
bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int get_lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = LG - 1; i >= 0; i--) {
        if (up[i][u] != 0 && !is_anc(up[i][u], v)) u = up[i][u];
    }
    return up[0][u];
}

bool covered(int u, int v, int lca) {
    int cnt = fen.sum(tin[u]) + fen.sum(tin[v]) - 2 * fen.sum(tin[lca]) + mark[lca];
    return cnt > 0;
}

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

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int lca = get_lca(u, v);
        byDep[dep[lca]].push_back({u, v, lca});
    }
    vector<int> ans;
    for (int d = n; d >= 0; d--) {
        for (auto [u, v, lca] : byDep[d]) {
            if (covered(u, v, lca)) continue;
            mark[lca] = 1;
            ans.push_back(lca);
            fen.upd_range(tin[lca], tout[lca], 1);
        }
    }
    cout << ans.size() << endl;
    for (int i : ans) cout << i << " ";
    cout << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...