제출 #826411

#제출 시각아이디문제언어결과실행 시간메모리
8264118pete8Railway (BOI17_railway)C++14
0 / 100
102 ms46432 KiB
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#define int long long
#define mod 1000000007
#define int long long
const int mxn=1e5,lg=20,inf=1e18;
vector<pii>e,adj[mxn+10];
int h[mxn+10],up[mxn+10][lg+10],add[mxn+10],ans[mxn+10];
bool cmp(int a,int b){return h[a]>h[b];}
void solve(int cur,int p){
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        up[i.f][0]=cur;
        h[i.f]=h[cur]+1;
        solve(i.f,cur);
    }
}
int push(int cur,int p){
    int cnt=add[cur],g;
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        g=push(i.f,cur);
        ans[i.s]+=g;
        cnt+=g;
    }
    return cnt;
}
int lca(int a,int b){
    if(h[a]<h[b])swap(a,b);
    int k=h[a]-h[b];
    for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
    if(a==b)return a;
    for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
    return up[a][0];
}
bitset<mxn+10>vis;
int32_t main(){
    fastio
    int n,m,k;cin>>n>>m>>k;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        e.pb({u,v});
    }
    solve(1,-1);
    for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)up[j][i]=up[up[j][i-1]][i-1];
    while(m--){
        int a;cin>>a;
        int node=-1;
        vector<int>an(a);
        for(int i=0;i<a;i++)cin>>an[i];
        sort(an.begin(),an.end(),cmp);
        node=an[0];
        vis.reset();
        for(int i=1;i<a;i++){
            node=lca(node,an[i]);
            vis[node]=true;
            add[node]--;
        }
        for(auto i:an)if(!vis[i])add[i]++;
    }
    push(1,-1);
    vector<int>v;
    for(int i=0;i<n-1;i++)if(ans[i]>=k)v.pb(i+1);
    cout<<v.size()<<'\n';
    for(auto i:v)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...