제출 #1352957

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

const int N = 1e5 + 10;

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

void dfs(int node, int parent){
    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 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);
        edges.push_back({u, v});
    }
    dfs(1, 1);
    for(int i = 0; i < m; i++){
        int s;
        cin >> s;
        assert(s == 2);
        int u, v;
        cin >> u >> v;
        val[u]++;
        val[v]++;
        val[lca(u, v)] -= 2;
    }
    // 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];
        if(up[u][0] != v) swap(u, v);
        if(val[u] >= 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...