제출 #1359893

#제출 시각아이디문제언어결과실행 시간메모리
1359893mine255Railway (BOI17_railway)C++20
100 / 100
116 ms21148 KiB
#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
#define ii pair<int,int>
#define lii pair<ll,ll>
#define fi first
#define se second
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

int n,m; ll k;
vector<ii> a[100007];

int cnt_id = 0;
int id[100007];
int rid[100007];
int par[100007];
int h[100007];
int head[100007];
int sz[100007];
int edge[100007];

int s;
int b[100007];

bool cmp(int a, int b) {
    return id[a] < id[b];
}

void dfs(int i) {
    sz[i] = 1;

    for (ii &x : a[i]) {
        int j = x.fi;
        int e = x.se;

        if (j == par[i]) continue;

        par[j] = i;
        h[j] = h[i] + 1;
        edge[j] = e;

        dfs(j);

        sz[i] += sz[j];
        if (sz[j] > sz[a[i][0].fi] || a[i][0].fi == par[i]) swap(x,a[i][0]);
    }
}

void hld(int i) {
    id[i] = ++cnt_id;
    rid[cnt_id] = i;

    for (ii x : a[i]) {
        int j = x.fi;

        if (j == par[i]) continue;

        head[j] = (j == a[i][0].fi ? head[i] : j);

        hld(j);
    }
}

ll lazy[400007];

void push(int id) {
    lazy[2*id] += lazy[id];
    lazy[2*id+1] += lazy[id];

    lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, ll val) {
    if (l > v || u > r) return;
    if (u <= l && r <= v) {
        lazy[id] += val;
        return;
    }

    int mid = (l + r) >> 1;
    push(id);

    update(2*id,l,mid,u,v,val);
    update(2*id+1,mid+1,r,u,v,val);
}

vector<int> res;

void get(int id, int l, int r) {
    if (l == r) {
        int node = rid[l];
        if (lazy[id] >= k) res.push_back(edge[node]);
        return;
    }

    int mid = (l + r) >> 1;
    push(id);

    get(2*id,l,mid);
    get(2*id+1,mid+1,r);
}

void up(int u, int v) {
    while (head[u] != head[v]) {
        if (h[head[u]] < h[head[v]]) swap(u,v);

        update(1,1,n,id[head[u]],id[u],1);
        u = par[head[u]];
    }

    if (h[u] < h[v]) swap(u,v);

    update(1,1,n,id[v]+1,id[u],1);
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    #ifdef EMERGENCY_DEBUG
    freopen(_FILE".inp","r",stdin);
    freopen(_FILE".out","w",stdout);
    #endif

     cin >> n >> m >> k;
     k *= 2;

     for (int i=1; i<n; i++) {
        int u,v;
        cin >> u >> v;

        a[u].push_back({v,i});
        a[v].push_back({u,i});
     }

    dfs(1);
    head[1] = 1;
    hld(1);

    while (m--) {
        cin >> s;

        for (int i=1; i<=s; i++) {
            cin >> b[i];
        }

        sort(b+1,b+s+1,cmp);
        
        for (int i=2; i<=s; i++) {
            up(b[i-1],b[i]);
        }
        up(b[s],b[1]);
    }

    get(1,1,n);

    cout << res.size() << '\n';
    sort(res.begin(),res.end());

    for (int i : res) cout << i << ' ';

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…