Submission #1318940

#TimeUsernameProblemLanguageResultExecution timeMemory
1318940wangzhiyi33Railway (BOI17_railway)C++20
100 / 100
195 ms46940 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;

vector<ii>adj[maxn+2];
int n,m,k,sz[maxn+2];
vector<int>isi[maxn+2],ans;
map<int,int>freq[maxn+2];
int slh[maxn+2];

void dfs(int cur,int par,int edge){
    for(auto [x,id] : adj[cur]){
        if(x==par)continue;
        dfs(x,cur,id);

        if(freq[x].size()>freq[cur].size()){
            swap(freq[x],freq[cur]);
            swap(slh[x],slh[cur]);
        }

        for(auto y : freq[x]){
            freq[cur][y.fir]+=y.sec;
            if(freq[cur][y.fir]==sz[y.fir]){
                slh[cur]++;
            }
        }
    }

    for(auto x : isi[cur]){
        freq[cur][x]++;
        if(freq[cur][x]==sz[x]){
            slh[cur]++;
        }
    }

    if(freq[cur].size()-slh[cur]>=k){
        ans.pb(edge);
    }
}

signed main(){
    cin>>n>>m>>k;
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].pb({v,q});
        adj[v].pb({u,q});
    }
    for(int q=1;q<=m;q++){
        cin>>sz[q];
        for(int w=1;w<=sz[q];w++){
            int x; cin>>x;
            isi[x].pb(q);
        }
    }
    dfs(1,0,0);

    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto x : ans){
        cout<<x<<' ';
    }
    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...