제출 #757636

#제출 시각아이디문제언어결과실행 시간메모리
757636adaawfRailway (BOI17_railway)C++14
59 / 100
125 ms25668 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> g[100005];
vector<int> res;
int k, c[100005], pp[100005][20], d[100005], dd[100005], a[200005], z = 1;
void dfs(int x, int p) {
    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 dfs2(int x, int p, int y) {
    for (auto w : g[x]) {
        if (w.first == p) continue;
        c[x] += dfs2(w.first, x, w.second);
    }
    if (c[x] >= k * 2 && y != 0) {
        res.push_back(y);
    }
    return c[x];
}
int lca(int x, int y) {
    int k = 19;
    if (d[x] < d[y]) swap(x, y);
    while (k >= 0 && d[x] > d[y]) {
        if (d[pp[x][k]] >= d[y]) {
            x = pp[x][k];
        }
        k--;
    }
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (pp[x][i] != pp[y][i]) {
            x = pp[x][i];
            y = pp[y][i];
        }
    }
    return pp[x][0];
}
bool cmp(int aa, int bb) {
    return dd[aa] < dd[bb];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    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, -1);
    for (int i = 1; i <= m; i++) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, a + n, cmp);
        a[n] = a[0];
        for (int i = 0; i < n; i++) {
            int x = a[i], y = a[i + 1], z = lca(x, y);
            c[x]++;
            c[y]++;
            c[z] -= 2;
        }
    }
    dfs2(1, -1, 0);
    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...