제출 #1355691

#제출 시각아이디문제언어결과실행 시간메모리
1355691njoopRailway (BOI17_railway)C++20
0 / 100
66 ms47288 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> g, p;
vector<int> d, add, ans, tin;
int tim;

void dfs(int no, int rt, int dis) {
    if(rt != -1) p[no][0] = rt;
    d[no] = dis;
    tin[no] = tim;
    tim++;
    for(auto i: g[no]) {
        if(i == rt) continue;
        dfs(i, no, dis+1);
    }
}

int lca(int u, int v) {
    if(d[u] > d[v]) swap(u, v);
    int k = d[v]-d[u];
    for(int i=0; i<=30; i++) {
        if(k & (1 << i)) v = p[v][i];
    }
    if(u == v) return u;
    for(int i=30; i>=0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

void dfs2(int no, int rt) {
    ans[no] += add[no];
    for(auto i: g[no]) {
        if(i == rt) continue;
        dfs2(i, no);
        ans[no] += ans[i];
    }
}

void update(int u, int v) {
    u = p[u][0];
    v = p[u][0];
    add[lca(u, v)]--;
    add[p[lca(u, v)][0]]--;
    add[u]++;
    add[v]++;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    g.assign(n+2, vector<int>());
    p.assign(n+2, vector<int>(32, 0));
    vector<pair<int, int>> edge;
    vector<int> ch;
    d.assign(n+2, 0); ans.assign(n+2, 0);
    add.assign(n+2, 0); edge.assign(n+2, {0, 0});
    tin.assign(n+2, 0);
    for(int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge[i].first = u;
        edge[i].second = v;
    }
    dfs(1, -1, 0);
    for(int i=1; i<=30; i++) {
        for(int j=1; j<=n; j++) {
            p[j][i] = p[p[j][i-1]][i-1];
        }
    }
    while(m--) {
        int s;
        cin >> s;
        vector<pair<int, int>> node;
        while(s--) {
            int u;
            cin >> u;
            node.push_back({tin[u], u});
        }
        sort(node.begin(), node.end());
        node.push_back(node.front());
        for(int i=0; i<node.size()-1; i++) {
            update(node[i].second, node[i+1].second);
        }
    }
    add[1] += add[0];
    dfs2(1, -1);
    for(int i=1; i<=n; i++) {
        int u = edge[i].first, v = edge[i].second;
        if(d[u] > d[v]) swap(u, v);
        if(ans[u] >= 2*k) ch.push_back(i);
    }
    cout << ch.size() << "\n";
    for(auto i: ch) cout << i << " ";
}
#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...