#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int > g[N];
set <int> st1[N],st2[N];
int jmp[20][N];
int d[N];
map <pair <int,int> ,int> mp;
int n,m,k;
void dfs(int v,int p){
jmp[0][v]=p;
for(auto to : g[v]){
if(to!=p){
d[to]=d[v]+1;
dfs(to,v);
}
}
}
int lca(int v,int u){
if(d[u]<d[v])swap(u,v);
for(int i=19;i>=0;i--){
if(d[jmp[i][u]]>=d[v]){
u=jmp[i][u];
}
}
if(u==v)return v;
for(int i=19;i>=0;i--){
if(jmp[i][u]!=jmp[i][v]){
u=jmp[i][u];
v=jmp[i][v];
}
}
return jmp[0][v];
}
vector <int> ans;
void calc(int v,int p){
int mx=st1[v].size();
int node=v;
for(auto to : g[v]){
if(to!=p){
calc(to,v);
if(st1[to].size()>mx){
mx=st1[to].size();
node=to;
}
}
}
swap(st1[v],st1[node]);
for(auto to : g[v]){
if(to!=p){
for(auto x : st1[to])st1[v].insert(x);
st1[to].clear();
}
}
for(auto x : st2[v])st1[v].erase(x);
if(st1[v].size()>=k){
ans.pb(v);
}
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
mp[{u,v}]=i;
g[u].pb(v);
g[v].pb(u);
}
dfs(1,1);
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
jmp[i][j]=jmp[i-1][jmp[i-1][j]];
}
}
for(int i=1;i<=m;i++){
int s;
cin>>s;
int p=0;
for(int j=0;j<s;j++){
int x;
cin>>x;
if(p==0)p=x;
else {
p=lca(p,x);
}
st1[x].insert(i);
}
st2[p].insert(i);
}
calc(1,0);
vector <int> res;
for(auto x : ans){
if(mp[{x,jmp[0][x]}])res.pb(mp[{x,jmp[0][x]}]);
else res.pb(mp[{jmp[0][x],x}]);
}
sort(all(res));
cout<<res.size()<<"\n";
for(auto x : res)cout<<x<<" ";
}
/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
*/
Compilation message
railway.cpp: In function 'void calc(long long int, long long int)':
railway.cpp:47:30: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
47 | if(st1[to].size()>mx){
| ~~~~~~~~~~~~~~^~~
railway.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
61 | if(st1[v].size()>=k){
| ~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
28252 KB |
Output is correct |
2 |
Correct |
13 ms |
29532 KB |
Output is correct |
3 |
Correct |
13 ms |
29532 KB |
Output is correct |
4 |
Correct |
5 ms |
28252 KB |
Output is correct |
5 |
Correct |
7 ms |
28416 KB |
Output is correct |
6 |
Correct |
15 ms |
30484 KB |
Output is correct |
7 |
Correct |
13 ms |
29636 KB |
Output is correct |
8 |
Correct |
14 ms |
29796 KB |
Output is correct |
9 |
Correct |
14 ms |
29740 KB |
Output is correct |
10 |
Correct |
5 ms |
28256 KB |
Output is correct |
11 |
Correct |
5 ms |
28252 KB |
Output is correct |
12 |
Correct |
8 ms |
28444 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
5 ms |
28404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
28252 KB |
Output is correct |
2 |
Correct |
13 ms |
29532 KB |
Output is correct |
3 |
Correct |
13 ms |
29532 KB |
Output is correct |
4 |
Correct |
5 ms |
28252 KB |
Output is correct |
5 |
Correct |
7 ms |
28416 KB |
Output is correct |
6 |
Correct |
15 ms |
30484 KB |
Output is correct |
7 |
Correct |
13 ms |
29636 KB |
Output is correct |
8 |
Correct |
14 ms |
29796 KB |
Output is correct |
9 |
Correct |
14 ms |
29740 KB |
Output is correct |
10 |
Correct |
5 ms |
28256 KB |
Output is correct |
11 |
Correct |
5 ms |
28252 KB |
Output is correct |
12 |
Correct |
8 ms |
28444 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
5 ms |
28404 KB |
Output is correct |
15 |
Correct |
51 ms |
33624 KB |
Output is correct |
16 |
Correct |
62 ms |
33752 KB |
Output is correct |
17 |
Correct |
50 ms |
33684 KB |
Output is correct |
18 |
Correct |
15 ms |
30552 KB |
Output is correct |
19 |
Correct |
15 ms |
29792 KB |
Output is correct |
20 |
Correct |
64 ms |
34924 KB |
Output is correct |
21 |
Correct |
53 ms |
34640 KB |
Output is correct |
22 |
Correct |
5 ms |
28252 KB |
Output is correct |
23 |
Correct |
13 ms |
29732 KB |
Output is correct |
24 |
Correct |
15 ms |
29528 KB |
Output is correct |
25 |
Correct |
7 ms |
28336 KB |
Output is correct |
26 |
Correct |
6 ms |
28400 KB |
Output is correct |
27 |
Correct |
14 ms |
30556 KB |
Output is correct |
28 |
Correct |
13 ms |
29652 KB |
Output is correct |
29 |
Correct |
12 ms |
29572 KB |
Output is correct |
30 |
Correct |
12 ms |
29796 KB |
Output is correct |
31 |
Correct |
6 ms |
28328 KB |
Output is correct |
32 |
Correct |
6 ms |
28260 KB |
Output is correct |
33 |
Correct |
5 ms |
28252 KB |
Output is correct |
34 |
Correct |
5 ms |
28440 KB |
Output is correct |
35 |
Correct |
5 ms |
28248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
61224 KB |
Output is correct |
2 |
Correct |
5 ms |
28248 KB |
Output is correct |
3 |
Correct |
248 ms |
58824 KB |
Output is correct |
4 |
Correct |
244 ms |
57680 KB |
Output is correct |
5 |
Correct |
185 ms |
58016 KB |
Output is correct |
6 |
Correct |
211 ms |
60472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
52688 KB |
Output is correct |
2 |
Correct |
213 ms |
48072 KB |
Output is correct |
3 |
Correct |
272 ms |
47844 KB |
Output is correct |
4 |
Correct |
247 ms |
47664 KB |
Output is correct |
5 |
Correct |
292 ms |
47652 KB |
Output is correct |
6 |
Correct |
190 ms |
53068 KB |
Output is correct |
7 |
Correct |
183 ms |
52820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
52688 KB |
Output is correct |
2 |
Correct |
213 ms |
48072 KB |
Output is correct |
3 |
Correct |
272 ms |
47844 KB |
Output is correct |
4 |
Correct |
247 ms |
47664 KB |
Output is correct |
5 |
Correct |
292 ms |
47652 KB |
Output is correct |
6 |
Correct |
190 ms |
53068 KB |
Output is correct |
7 |
Correct |
183 ms |
52820 KB |
Output is correct |
8 |
Correct |
169 ms |
51976 KB |
Output is correct |
9 |
Correct |
172 ms |
51920 KB |
Output is correct |
10 |
Correct |
166 ms |
58680 KB |
Output is correct |
11 |
Correct |
179 ms |
58564 KB |
Output is correct |
12 |
Correct |
112 ms |
44624 KB |
Output is correct |
13 |
Correct |
113 ms |
44796 KB |
Output is correct |
14 |
Correct |
166 ms |
45372 KB |
Output is correct |
15 |
Correct |
192 ms |
45072 KB |
Output is correct |
16 |
Correct |
302 ms |
47808 KB |
Output is correct |
17 |
Correct |
280 ms |
47712 KB |
Output is correct |
18 |
Correct |
242 ms |
47936 KB |
Output is correct |
19 |
Correct |
229 ms |
48468 KB |
Output is correct |
20 |
Correct |
210 ms |
53360 KB |
Output is correct |
21 |
Correct |
198 ms |
53848 KB |
Output is correct |
22 |
Correct |
204 ms |
53832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
28252 KB |
Output is correct |
2 |
Correct |
13 ms |
29532 KB |
Output is correct |
3 |
Correct |
13 ms |
29532 KB |
Output is correct |
4 |
Correct |
5 ms |
28252 KB |
Output is correct |
5 |
Correct |
7 ms |
28416 KB |
Output is correct |
6 |
Correct |
15 ms |
30484 KB |
Output is correct |
7 |
Correct |
13 ms |
29636 KB |
Output is correct |
8 |
Correct |
14 ms |
29796 KB |
Output is correct |
9 |
Correct |
14 ms |
29740 KB |
Output is correct |
10 |
Correct |
5 ms |
28256 KB |
Output is correct |
11 |
Correct |
5 ms |
28252 KB |
Output is correct |
12 |
Correct |
8 ms |
28444 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
5 ms |
28404 KB |
Output is correct |
15 |
Correct |
51 ms |
33624 KB |
Output is correct |
16 |
Correct |
62 ms |
33752 KB |
Output is correct |
17 |
Correct |
50 ms |
33684 KB |
Output is correct |
18 |
Correct |
15 ms |
30552 KB |
Output is correct |
19 |
Correct |
15 ms |
29792 KB |
Output is correct |
20 |
Correct |
64 ms |
34924 KB |
Output is correct |
21 |
Correct |
53 ms |
34640 KB |
Output is correct |
22 |
Correct |
5 ms |
28252 KB |
Output is correct |
23 |
Correct |
13 ms |
29732 KB |
Output is correct |
24 |
Correct |
15 ms |
29528 KB |
Output is correct |
25 |
Correct |
7 ms |
28336 KB |
Output is correct |
26 |
Correct |
6 ms |
28400 KB |
Output is correct |
27 |
Correct |
14 ms |
30556 KB |
Output is correct |
28 |
Correct |
13 ms |
29652 KB |
Output is correct |
29 |
Correct |
12 ms |
29572 KB |
Output is correct |
30 |
Correct |
12 ms |
29796 KB |
Output is correct |
31 |
Correct |
6 ms |
28328 KB |
Output is correct |
32 |
Correct |
6 ms |
28260 KB |
Output is correct |
33 |
Correct |
5 ms |
28252 KB |
Output is correct |
34 |
Correct |
5 ms |
28440 KB |
Output is correct |
35 |
Correct |
5 ms |
28248 KB |
Output is correct |
36 |
Correct |
303 ms |
61224 KB |
Output is correct |
37 |
Correct |
5 ms |
28248 KB |
Output is correct |
38 |
Correct |
248 ms |
58824 KB |
Output is correct |
39 |
Correct |
244 ms |
57680 KB |
Output is correct |
40 |
Correct |
185 ms |
58016 KB |
Output is correct |
41 |
Correct |
211 ms |
60472 KB |
Output is correct |
42 |
Correct |
205 ms |
52688 KB |
Output is correct |
43 |
Correct |
213 ms |
48072 KB |
Output is correct |
44 |
Correct |
272 ms |
47844 KB |
Output is correct |
45 |
Correct |
247 ms |
47664 KB |
Output is correct |
46 |
Correct |
292 ms |
47652 KB |
Output is correct |
47 |
Correct |
190 ms |
53068 KB |
Output is correct |
48 |
Correct |
183 ms |
52820 KB |
Output is correct |
49 |
Correct |
169 ms |
51976 KB |
Output is correct |
50 |
Correct |
172 ms |
51920 KB |
Output is correct |
51 |
Correct |
166 ms |
58680 KB |
Output is correct |
52 |
Correct |
179 ms |
58564 KB |
Output is correct |
53 |
Correct |
112 ms |
44624 KB |
Output is correct |
54 |
Correct |
113 ms |
44796 KB |
Output is correct |
55 |
Correct |
166 ms |
45372 KB |
Output is correct |
56 |
Correct |
192 ms |
45072 KB |
Output is correct |
57 |
Correct |
302 ms |
47808 KB |
Output is correct |
58 |
Correct |
280 ms |
47712 KB |
Output is correct |
59 |
Correct |
242 ms |
47936 KB |
Output is correct |
60 |
Correct |
229 ms |
48468 KB |
Output is correct |
61 |
Correct |
210 ms |
53360 KB |
Output is correct |
62 |
Correct |
198 ms |
53848 KB |
Output is correct |
63 |
Correct |
204 ms |
53832 KB |
Output is correct |
64 |
Correct |
215 ms |
53348 KB |
Output is correct |
65 |
Correct |
347 ms |
47372 KB |
Output is correct |
66 |
Correct |
230 ms |
45044 KB |
Output is correct |
67 |
Correct |
216 ms |
45356 KB |
Output is correct |
68 |
Correct |
124 ms |
42716 KB |
Output is correct |
69 |
Correct |
133 ms |
42896 KB |
Output is correct |
70 |
Correct |
223 ms |
54220 KB |
Output is correct |
71 |
Correct |
168 ms |
51536 KB |
Output is correct |
72 |
Correct |
5 ms |
12120 KB |
Output is correct |
73 |
Correct |
12 ms |
14940 KB |
Output is correct |
74 |
Correct |
13 ms |
15148 KB |
Output is correct |
75 |
Correct |
5 ms |
12124 KB |
Output is correct |
76 |
Correct |
5 ms |
12124 KB |
Output is correct |
77 |
Correct |
15 ms |
15964 KB |
Output is correct |
78 |
Correct |
13 ms |
15016 KB |
Output is correct |
79 |
Correct |
13 ms |
15196 KB |
Output is correct |
80 |
Correct |
18 ms |
15196 KB |
Output is correct |
81 |
Correct |
7 ms |
12120 KB |
Output is correct |
82 |
Correct |
5 ms |
12124 KB |
Output is correct |
83 |
Correct |
5 ms |
12120 KB |
Output is correct |
84 |
Correct |
5 ms |
12072 KB |
Output is correct |
85 |
Correct |
5 ms |
12120 KB |
Output is correct |
86 |
Correct |
53 ms |
19028 KB |
Output is correct |
87 |
Correct |
58 ms |
19024 KB |
Output is correct |
88 |
Correct |
51 ms |
19092 KB |
Output is correct |
89 |
Correct |
15 ms |
15964 KB |
Output is correct |
90 |
Correct |
14 ms |
15196 KB |
Output is correct |
91 |
Correct |
53 ms |
20400 KB |
Output is correct |
92 |
Correct |
52 ms |
20204 KB |
Output is correct |
93 |
Correct |
6 ms |
12120 KB |
Output is correct |
94 |
Correct |
312 ms |
61176 KB |
Output is correct |
95 |
Correct |
292 ms |
58828 KB |
Output is correct |
96 |
Correct |
232 ms |
57808 KB |
Output is correct |
97 |
Correct |
222 ms |
58164 KB |
Output is correct |
98 |
Correct |
200 ms |
60280 KB |
Output is correct |
99 |
Correct |
271 ms |
47840 KB |
Output is correct |
100 |
Correct |
270 ms |
47696 KB |
Output is correct |
101 |
Correct |
269 ms |
47700 KB |
Output is correct |
102 |
Correct |
247 ms |
48136 KB |
Output is correct |
103 |
Correct |
200 ms |
53052 KB |
Output is correct |
104 |
Correct |
206 ms |
53728 KB |
Output is correct |
105 |
Correct |
201 ms |
53200 KB |
Output is correct |
106 |
Correct |
178 ms |
52076 KB |
Output is correct |
107 |
Correct |
175 ms |
51832 KB |
Output is correct |
108 |
Correct |
179 ms |
58684 KB |
Output is correct |
109 |
Correct |
191 ms |
58496 KB |
Output is correct |
110 |
Correct |
129 ms |
44868 KB |
Output is correct |
111 |
Correct |
132 ms |
44708 KB |
Output is correct |
112 |
Correct |
173 ms |
45152 KB |
Output is correct |
113 |
Correct |
190 ms |
45136 KB |
Output is correct |