Submission #1115823

#TimeUsernameProblemLanguageResultExecution timeMemory
1115823vjudge1Railway (BOI17_railway)C++17
100 / 100
97 ms23748 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k, x;
vector<pair<int, int>> g[100005];
int c[100005], pp[100005][20], d[100005], dd[100005], z = 1;
void dfs(int x, int p = 0) {
    d[x] = d[p] + 1;
    dd[x] = z++;
    pp[x][0] = p;
    for (int i = 1; i < 20; i++) {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
    }
    for (auto w : g[x]) {
        if (w.first == p) continue;
        dfs(w.first, x);
    }
}
int lca(int a, int b) {
    int i = 19;
    if (d[a] < d[b]) swap(a, b);
    while (i >= 0 && d[a] > d[b]) {
        if (d[pp[a][i]] >= d[b]) {
            a = pp[a][i];
        }
        i--;
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (pp[a][i] != pp[b][i]) {
            a = pp[a][i];
            b = pp[b][i];
        }
    }
    return pp[a][0];
}
vector<int> res;
int dfs2(int x, int p = 0, int y = 0) {
    for (auto w : g[x]) {
        if (w.first == p) continue;
        c[x] += dfs2(w.first, x, w.second);
    }
    if (c[x] >= k * 2 && y) {
        res.push_back(y);
    }
    return c[x];
}
bool cmp(int aa, int bb) {
    return dd[aa] < dd[bb];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1);
    for (int i = 1; i <= m; i++) {
        cin >> x;
        vector<int> v(x);
        for (int i = 0; i < x; i++) {
            cin >> v[i];
        }
        sort(v.begin(), v.end(), cmp);
        v.push_back(v[0]);
        for (int i = 0; i < x; i++) {
            int x = v[i], y = v[i + 1], z = lca(x, y);
            c[x]++;
            c[y]++;
            c[z] -= 2;
        }
    }
    dfs2(1);
    cout << res.size() << '\n';
    sort(res.begin(), res.end());
    for (int w : res) {
        cout << w << " ";
    }
}
#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...