제출 #1352955

#제출 시각아이디문제언어결과실행 시간메모리
1352955vahagngRailway (BOI17_railway)C++20
0 / 100
57 ms22156 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, k, up[N][19], depth[N], val[N], tin[N], timer, deg[N];
vector<int> adj[N];

void dfs(int node, int parent){
    tin[node] = ++timer;
    up[node][0] = parent;
    for(int i = 1; i < 19; i++){
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for(auto i : adj[node]){
        if(i == parent) continue;
        depth[i] = depth[node] + 1;
        dfs(i, node);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int i = 0; i < 19; i++){
        if(d & (1 << i)){
            u = up[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 18; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void dfs0(int node, int parent){
    for(auto i : adj[node]){
        if(i == parent) continue;
        dfs0(i, node);
        val[node] += val[i];
    }
}

int p[N];

int main(){
    cin >> n >> m >> k;
    vector<pair<int,int>> edges;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
        edges.push_back({u, v});
    }
    int r = -1;
    for(int i = 1; i <= n; i++){
        if(deg[i] == 1){
            r = i;
            break;
        }
    }
    dfs(r, r);
    for(int i = 0; i < m; i++){
        int s;
        cin >> s;
        int mn = n + 1, mx = 0;
        while(s--){
            int u;
            cin >> u;
            mn = min(mn, tin[u]);
            mx = max(mx, tin[u]);
        }
        p[mn]++;
        p[mx]--;
    }
    for(int i = 1; i <= n - 1; i++){
        p[i] += p[i - 1];
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 0; j < 18; j++){
    //         cerr << "up[" << i << "][" << j << "] = " << up[i][j] << endl;
    //     }
    // }
    dfs0(1, 1);
    vector<int> res;
    for(int i = 0; i < n - 1; i++){
        auto [u, v] = edges[i];
        int T = min(tin[u], tin[v]);
        int T2 = max(tin[u], tin[v]);
        if(p[T] - p[T - 1] >= k){
            res.push_back(i + 1);
        }
    }
    cout << res.size() << endl;
    for(auto i : res) cout << i << ' ';
    cout << endl;
}
#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...