#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>v[maxn], resp;
int pre[maxn], pos[maxn], k, tmp, dp[maxn][20], pai[maxn], qtd[maxn], prof[maxn];
map<pair<int,int>,int>imp;
void dfs(int u){
tmp++;
pre[u]=tmp;
for(int viz : v[u]){
if(pre[viz]) continue;
prof[viz]=prof[u]+1;
pai[viz]=u;
dfs(viz);
}
pos[u]=tmp;
}
int lca(int a, int b){
if(prof[a]<prof[b]) swap(a,b);
int d=prof[a]-prof[b];
for(int k=0;k<20;k++) if(d&(1<<k)) a=dp[a][k];
if(a==b) return a;
for(int k=19;k>=0;k--){
int na=dp[a][k], nb=dp[b][k];
if(na!=nb){
a=na; b=nb;
}
}
return pai[a];
}
void calc(int u, int pai){
for(int viz : v[u]){
if(viz==pai) continue;
calc(viz,u);
qtd[u]+=qtd[viz];
}
if(qtd[u]>=k) resp.push_back(imp[{u,pai}]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m; cin >> n >> m >> k;
k*=2;
for(int i=1;i<n;i++){
int a, b; cin >> a >> b;
imp[{a,b}]=imp[{b,a}]=i;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
pai[1]=1;
for(int i=1;i<=n;i++) dp[i][0]=pai[i];
for(int k=1;k<20;k++)
for(int i=1;i<=n;i++) dp[i][k]=dp[dp[i][k-1]][k-1];
for(int i=1;i<=m;i++){
vector<pair<int,int>>aux;
int x; cin >> x;
for(int j=1;j<=x;j++){
int a; cin >> a;
aux.push_back({pre[a],a});
}
sort(aux.begin(),aux.end());
int last=aux.back().second;
for(auto p : aux){
qtd[last]++; qtd[p.second]++;
qtd[lca(last,p.second)]-=2;
last=p.second;
}
}
calc(1,1);
sort(resp.begin(),resp.end());
cout << resp.size() << endl;
for(int a : resp) cout << a << " ";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |