#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int marc[MAXN], deg[MAXN], nivel[MAXN];
int dp[20][MAXN];
vector<int> adj[MAXN];
int root = 1, nivel_root = 0;
set<int> active, leaf;
void dfs(int v, int p){
for(auto u : adj[v]){
if(u != p){
nivel[u] = nivel[v] + 1;
dp[0][u] = v;
dfs(u, v);
}
}
}
int jump(int v){
for(int k=19; k>=0; k--){
if(nivel[dp[k][v]] < nivel_root) continue;
if(!active.count(dp[k][v])) v = dp[k][v];
}
v = dp[0][v];
return v;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
vector<pair<int, int>> edges;
for(int i=1; i<n; i++){
int a, b; cin >> a >> b;
edges.push_back({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
deg[a] ++;
deg[b] ++;
}
dp[0][root] = 1;
dfs(root, root);
for(int k=1; k<20; k++){
for(int i=1; i<=n; i++){
dp[k][i] = dp[k - 1][dp[k - 1][i]];
}
}
for(int i=1; i<=n; i++){
active.insert(i);
if(deg[i] == 1) leaf.insert(i);
}
while(m--){
int s; cin >> s;
vector<int> vtx(s);
for(int i=0; i<s; i++){
cin >> vtx[i];
if(!active.count(vtx[i])) vtx[i] = jump(vtx[i]);
marc[vtx[i]] ++;
}
queue<int> q;
for(auto x : leaf) q.push(x);
while(!q.empty()){
int v = q.front(); q.pop();
if(marc[v]) continue;
if(v == root) nivel_root ++;
leaf.erase(v);
active.erase(v);
for(auto u : adj[v]){
deg[u] --;
if(deg[u] == 1){
leaf.insert(u);
q.push(u);
}
}
}
for(int i=0; i<s; i++) marc[vtx[i]] --;
}
cout << (int) active.size() - 1 << "\n";
for(int i=0; i<(int) edges.size(); i++){
if(active.count(edges[i].first) && active.count(edges[i].second)){
cout << i + 1 << " ";
}
}
cout << "\n";
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... |