Submission #260434

#TimeUsernameProblemLanguageResultExecution timeMemory
260434dolphingarlicRailway (BOI17_railway)C++14
100 / 100
324 ms23540 KiB
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, m, k;
vector<pair<int, int>> graph[100001];
int tin[100001], tout[100001], timer = 0, anc[100001][20], p_edge[100001];
int chosen[50001];
int bit1[100001], bit2[100001];

void dfs(int node = 1, int parent = 0) {
    tin[node] = ++timer;
    for (int i = 1; i < 20; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
    for (pair<int, int> i : graph[node]) if (i.first != parent) {
        anc[i.first][0] = node;
        p_edge[i.first] = i.second;
        dfs(i.first, node);
    }
    tout[node] = timer;
}

bool is_ancestor(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b) {
    if (is_ancestor(a, b)) return a;
    for (int i = 19; ~i; i--) {
        if (anc[a][i] && !is_ancestor(anc[a][i], b)) a = anc[a][i];
    }
    return anc[a][0];
}

void update(int bit[100001], int pos, int val) {
    for (; pos <= n; pos += pos & (-pos)) bit[pos] += val;
}

int query(int bit[100001], int a, int b) {
    int ans = 0;
    for (; b; b -= b & (-b)) ans += bit[b];
    for (a--; a; a -= a & (-a)) ans -= bit[a];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }

    dfs();

    while (m--) {
        int s, l;
        cin >> s;
        for (int i = 0; i < s; i++) {
            cin >> chosen[i];
            if (!i) l = chosen[i];
            else l = lca(l, chosen[i]);
        }
        for (int i = 0; i < s; i++) {
            int curr = chosen[i];
            if (curr == l) continue;
            for (int j = 19; ~j; j--) {
                int nxt = anc[curr][j];
                if (nxt && !is_ancestor(nxt, l) && !query(bit2, tin[nxt], tout[nxt])) {
                    update(bit1, tin[curr], 1);
                    update(bit2, tin[curr], 1);
                    update(bit1, tin[nxt], -1);
                    update(bit2, tin[nxt], -1);
                    curr = nxt;
                }
            }
            update(bit1, tin[curr], 1);
            update(bit2, tin[curr], 1);
            update(bit1, tin[anc[curr][0]], -1);
            update(bit2, tin[anc[curr][0]], -1);
        }
        for (int i = 0; i < s; i++) {
            int curr = chosen[i];
            if (curr == l) continue;
            for (int j = 19; ~j; j--) {
                int nxt = anc[curr][j];
                if (nxt && !is_ancestor(nxt, l) && query(bit2, tin[nxt], tout[nxt])) {
                    update(bit2, tin[curr], -1);
                    update(bit2, tin[nxt], 1);
                    curr = nxt;
                }
            }
            update(bit2, tin[curr], -1);
            update(bit2, tin[anc[curr][0]], 1);
        }
    }

    vector<int> ans;
    for (int i = 2; i <= n; i++) if (query(bit1, tin[i], tout[i]) >= k) {
        ans.push_back(p_edge[i]);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    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...
#Verdict Execution timeMemoryGrader output
Fetching results...