제출 #1350951

#제출 시각아이디문제언어결과실행 시간메모리
1350951msab3fRailway (BOI17_railway)C++20
100 / 100
91 ms29044 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100'000 + 10;
const int MAX_LG = 17;

int n, m, k, st[MAX_N], ft[MAX_N], h[MAX_N], par[MAX_N][MAX_LG], dp[MAX_N];
vector<pair<int, int>> adj[MAX_N];
vector<int> ans;

int vpar[MAX_N];
vector<int> vadj[MAX_N];

void pre_dfs(int u) {
    static int time = 0;
    st[u] = time++;
    for (int i = 1; i < MAX_LG; ++i) {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for (auto [v, e] : adj[u]) {
        if (v != par[u][0]) {
            par[v][0] = u;
            h[v] = h[u] + 1;
            pre_dfs(v);
        }
    }
    ft[u] = time;
}

int get_lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    for (int i = 0, diff = h[u] - h[v]; diff != 0; ++i, diff >>= 1) {
        if (diff & 1) u = par[u][i];
    }
    if (u == v) return u;
    for (int i = MAX_LG - 1; i >= 0; --i) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void add_dfs(int u) {
    dp[u] -= int(vadj[u].size()) - 1;
    for (int v : vadj[u]) {
        add_dfs(v);
    }
}

void final_dfs(int u) {
    for (auto [v, e] : adj[u]) {
        if (v != par[u][0]) {
            final_dfs(v);
            dp[u] += dp[v];
            if (dp[v] >= k) {
                ans.push_back(e);
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;

    for (int e = 1, u, v; e <= n - 1; ++e) {
        cin >> u >> v;
        adj[u].push_back({v, e});
        adj[v].push_back({u, e});
    }

    pre_dfs(1);

    while (m--) {
        int s;
        cin >> s;
        vector<int> V;
        for (int i = 0; i < s; ++i) {
            int v;
            cin >> v;
            V.push_back(v);
        }
        sort(V.begin(), V.end(), [&] (int u, int v) { return st[u] < st[v]; });
        for (int i = 0; i + 1 < s; ++i) {
            V.push_back(get_lca(V[i], V[i + 1]));
        }
        sort(V.begin(), V.end(), [&] (int u, int v) { return st[u] < st[v]; });
        V.erase(unique(V.begin(), V.end()), V.end());
        for (int i = 1; i < V.size(); ++i) {
            vpar[V[i]] = V[i - 1];
            while (ft[vpar[V[i]]] < ft[V[i]]) {
                vpar[V[i]] = vpar[vpar[V[i]]];
            }
            vadj[vpar[V[i]]].push_back(V[i]);
        }
        add_dfs(V[0]);
        --dp[V[0]];
        for (int v : V) {
            vpar[v] = 0;
            vadj[v].clear();
        }
    }

    final_dfs(1);

    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int e : ans) {
        cout << e << ' ';
    }
    cout << '\n';
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...