#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second
typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, M, K, psa[MM], dep[MM], son[MM], top[MM], fa[MM], sz[MM], in[MM], ot[MM], cnt;
vector<pair<int,int>> adj[MM];
vector<int> vdj[MM], ans;
void df1(int u, int pa=0) {
dep[u]=dep[pa]+1; fa[u]=pa; sz[u]=1; in[u]=++cnt;
for(auto &e:adj[u]) if(e.f!=pa) {
int v=e.f;
df1(v, u); sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v; }
ot[u]=++cnt;
}
void df2(int u, int pa=0) {
if(son[u]) {
top[son[u]]=top[u]; df2(son[u], u); }
for(auto &e:adj[u]) if(e.f!=pa&&e.f!=son[u]) {
df2(top[e.f]=e.f, u);
}
}
bool above(int u, int v) {
return in[u]<in[v]&&ot[v]<ot[u];
}
bool cmp(int u, int v) {
return in[u]<in[v];
}
int lca(int u, int v) {
for(; top[u]!=top[v]; u=fa[top[u]]) {
if(dep[top[u]]<dep[top[v]]) swap(u, v); }
return (dep[u]<dep[v]?u:v);
}
int buildvrt(vector<int> &vrt, int k) {
sort(begin(vrt), end(vrt), cmp);
for(int i=1; i<k; ++i) {
vrt.pb(lca(vrt[i-1], vrt[i])); }
sort(begin(vrt), end(vrt), cmp);
vrt.erase(unique(begin(vrt), end(vrt)), end(vrt));
vector<int> stk={vrt[0]};
for(int i=1; i<vrt.size(); ++i) {
int u=vrt[i];
while(stk.size()>=2&&!above(stk.back(), u)) {
vdj[stk[stk.size()-2]].pb(stk.back());
stk.pop_back(); }
stk.pb(u); }
while(stk.size()>=2) {
vdj[stk[stk.size()-2]].pb(stk.back());
stk.pop_back(); }
return stk[0];
}
void df3(int u, int pa=0) {
for(int &v:vdj[u]) if(v!=pa) ++psa[v], --psa[u], df3(v, u);
vdj[u].clear();
}
void df4(int u, int pa=0) {
for(auto &e:adj[u]) if(e.f!=pa) {
df4(e.f, u); psa[u]+=psa[e.f]; }
for(auto &e:adj[u]) if(e.f!=pa) {
if(psa[e.f]>=K) ans.pb(e.s);
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>N>>M>>K;
for(int i=1, u, v; i<N; ++i) {
cin>>u>>v;
adj[u].pb({v,i}); adj[v].pb({u,i}); }
df1(1); df2(top[1]=1);
for(int i=1, k; i<=M; ++i) {
cin>>k; vector<int> vrt;
for(int j=1, x; j<=k; ++j) cin>>x, vrt.pb(x);
df3( buildvrt(vrt, k)); }
df4(1);
sort(begin(ans), end(ans));
cout<<ans.size()<<el;
for(int i=0; i<ans.size(); ++i) cout<<ans[i]<<" \n"[i==ans.size()-1];
}
// MM
Compilation message
railway.cpp: In function 'int buildvrt(std::vector<int>&, int)':
railway.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=1; i<vrt.size(); ++i) {
| ~^~~~~~~~~~~
railway.cpp: In function 'int32_t main()':
railway.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=0; i<ans.size(); ++i) cout<<ans[i]<<" \n"[i==ans.size()-1];
| ~^~~~~~~~~~~
railway.cpp:95:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=0; i<ans.size(); ++i) cout<<ans[i]<<" \n"[i==ans.size()-1];
| ~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
8 ms |
5836 KB |
Output is correct |
3 |
Correct |
8 ms |
5836 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
8 ms |
6308 KB |
Output is correct |
7 |
Correct |
8 ms |
5836 KB |
Output is correct |
8 |
Correct |
7 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5020 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
8 ms |
5836 KB |
Output is correct |
3 |
Correct |
8 ms |
5836 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
8 ms |
6308 KB |
Output is correct |
7 |
Correct |
8 ms |
5836 KB |
Output is correct |
8 |
Correct |
7 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5020 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
36 ms |
6276 KB |
Output is correct |
16 |
Correct |
38 ms |
6280 KB |
Output is correct |
17 |
Correct |
36 ms |
6300 KB |
Output is correct |
18 |
Correct |
9 ms |
6180 KB |
Output is correct |
19 |
Correct |
8 ms |
5836 KB |
Output is correct |
20 |
Correct |
26 ms |
6236 KB |
Output is correct |
21 |
Correct |
30 ms |
6224 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
9 ms |
5836 KB |
Output is correct |
24 |
Correct |
8 ms |
5836 KB |
Output is correct |
25 |
Correct |
3 ms |
4940 KB |
Output is correct |
26 |
Correct |
3 ms |
5020 KB |
Output is correct |
27 |
Correct |
9 ms |
6348 KB |
Output is correct |
28 |
Correct |
8 ms |
5836 KB |
Output is correct |
29 |
Correct |
7 ms |
5708 KB |
Output is correct |
30 |
Correct |
7 ms |
5800 KB |
Output is correct |
31 |
Correct |
5 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
4 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
5016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
22848 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
90 ms |
22592 KB |
Output is correct |
4 |
Correct |
102 ms |
22024 KB |
Output is correct |
5 |
Correct |
94 ms |
23648 KB |
Output is correct |
6 |
Correct |
103 ms |
23360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
17424 KB |
Output is correct |
2 |
Correct |
94 ms |
14016 KB |
Output is correct |
3 |
Correct |
97 ms |
13648 KB |
Output is correct |
4 |
Correct |
108 ms |
13596 KB |
Output is correct |
5 |
Correct |
104 ms |
13636 KB |
Output is correct |
6 |
Correct |
80 ms |
17584 KB |
Output is correct |
7 |
Correct |
88 ms |
17524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
17424 KB |
Output is correct |
2 |
Correct |
94 ms |
14016 KB |
Output is correct |
3 |
Correct |
97 ms |
13648 KB |
Output is correct |
4 |
Correct |
108 ms |
13596 KB |
Output is correct |
5 |
Correct |
104 ms |
13636 KB |
Output is correct |
6 |
Correct |
80 ms |
17584 KB |
Output is correct |
7 |
Correct |
88 ms |
17524 KB |
Output is correct |
8 |
Correct |
92 ms |
18400 KB |
Output is correct |
9 |
Correct |
93 ms |
18500 KB |
Output is correct |
10 |
Correct |
98 ms |
23824 KB |
Output is correct |
11 |
Correct |
96 ms |
23696 KB |
Output is correct |
12 |
Correct |
72 ms |
12996 KB |
Output is correct |
13 |
Correct |
67 ms |
13036 KB |
Output is correct |
14 |
Correct |
105 ms |
13504 KB |
Output is correct |
15 |
Correct |
100 ms |
13636 KB |
Output is correct |
16 |
Correct |
95 ms |
13644 KB |
Output is correct |
17 |
Correct |
99 ms |
13684 KB |
Output is correct |
18 |
Correct |
102 ms |
13612 KB |
Output is correct |
19 |
Correct |
92 ms |
14024 KB |
Output is correct |
20 |
Correct |
82 ms |
17800 KB |
Output is correct |
21 |
Correct |
81 ms |
17856 KB |
Output is correct |
22 |
Correct |
82 ms |
17856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
8 ms |
5836 KB |
Output is correct |
3 |
Correct |
8 ms |
5836 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
8 ms |
6308 KB |
Output is correct |
7 |
Correct |
8 ms |
5836 KB |
Output is correct |
8 |
Correct |
7 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5020 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
36 ms |
6276 KB |
Output is correct |
16 |
Correct |
38 ms |
6280 KB |
Output is correct |
17 |
Correct |
36 ms |
6300 KB |
Output is correct |
18 |
Correct |
9 ms |
6180 KB |
Output is correct |
19 |
Correct |
8 ms |
5836 KB |
Output is correct |
20 |
Correct |
26 ms |
6236 KB |
Output is correct |
21 |
Correct |
30 ms |
6224 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
9 ms |
5836 KB |
Output is correct |
24 |
Correct |
8 ms |
5836 KB |
Output is correct |
25 |
Correct |
3 ms |
4940 KB |
Output is correct |
26 |
Correct |
3 ms |
5020 KB |
Output is correct |
27 |
Correct |
9 ms |
6348 KB |
Output is correct |
28 |
Correct |
8 ms |
5836 KB |
Output is correct |
29 |
Correct |
7 ms |
5708 KB |
Output is correct |
30 |
Correct |
7 ms |
5800 KB |
Output is correct |
31 |
Correct |
5 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
4 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
5016 KB |
Output is correct |
36 |
Correct |
96 ms |
22848 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
90 ms |
22592 KB |
Output is correct |
39 |
Correct |
102 ms |
22024 KB |
Output is correct |
40 |
Correct |
94 ms |
23648 KB |
Output is correct |
41 |
Correct |
103 ms |
23360 KB |
Output is correct |
42 |
Correct |
104 ms |
17424 KB |
Output is correct |
43 |
Correct |
94 ms |
14016 KB |
Output is correct |
44 |
Correct |
97 ms |
13648 KB |
Output is correct |
45 |
Correct |
108 ms |
13596 KB |
Output is correct |
46 |
Correct |
104 ms |
13636 KB |
Output is correct |
47 |
Correct |
80 ms |
17584 KB |
Output is correct |
48 |
Correct |
88 ms |
17524 KB |
Output is correct |
49 |
Correct |
92 ms |
18400 KB |
Output is correct |
50 |
Correct |
93 ms |
18500 KB |
Output is correct |
51 |
Correct |
98 ms |
23824 KB |
Output is correct |
52 |
Correct |
96 ms |
23696 KB |
Output is correct |
53 |
Correct |
72 ms |
12996 KB |
Output is correct |
54 |
Correct |
67 ms |
13036 KB |
Output is correct |
55 |
Correct |
105 ms |
13504 KB |
Output is correct |
56 |
Correct |
100 ms |
13636 KB |
Output is correct |
57 |
Correct |
95 ms |
13644 KB |
Output is correct |
58 |
Correct |
99 ms |
13684 KB |
Output is correct |
59 |
Correct |
102 ms |
13612 KB |
Output is correct |
60 |
Correct |
92 ms |
14024 KB |
Output is correct |
61 |
Correct |
82 ms |
17800 KB |
Output is correct |
62 |
Correct |
81 ms |
17856 KB |
Output is correct |
63 |
Correct |
82 ms |
17856 KB |
Output is correct |
64 |
Correct |
87 ms |
18124 KB |
Output is correct |
65 |
Correct |
102 ms |
13604 KB |
Output is correct |
66 |
Correct |
109 ms |
13620 KB |
Output is correct |
67 |
Correct |
106 ms |
13632 KB |
Output is correct |
68 |
Correct |
60 ms |
12920 KB |
Output is correct |
69 |
Correct |
61 ms |
12888 KB |
Output is correct |
70 |
Correct |
88 ms |
18456 KB |
Output is correct |
71 |
Correct |
89 ms |
18244 KB |
Output is correct |
72 |
Correct |
3 ms |
4940 KB |
Output is correct |
73 |
Correct |
8 ms |
5836 KB |
Output is correct |
74 |
Correct |
8 ms |
5764 KB |
Output is correct |
75 |
Correct |
3 ms |
4940 KB |
Output is correct |
76 |
Correct |
3 ms |
4940 KB |
Output is correct |
77 |
Correct |
9 ms |
6220 KB |
Output is correct |
78 |
Correct |
8 ms |
5960 KB |
Output is correct |
79 |
Correct |
7 ms |
5816 KB |
Output is correct |
80 |
Correct |
7 ms |
5836 KB |
Output is correct |
81 |
Correct |
3 ms |
4940 KB |
Output is correct |
82 |
Correct |
3 ms |
4940 KB |
Output is correct |
83 |
Correct |
3 ms |
5020 KB |
Output is correct |
84 |
Correct |
3 ms |
4940 KB |
Output is correct |
85 |
Correct |
4 ms |
4940 KB |
Output is correct |
86 |
Correct |
36 ms |
6296 KB |
Output is correct |
87 |
Correct |
37 ms |
6296 KB |
Output is correct |
88 |
Correct |
38 ms |
6396 KB |
Output is correct |
89 |
Correct |
9 ms |
6220 KB |
Output is correct |
90 |
Correct |
9 ms |
5836 KB |
Output is correct |
91 |
Correct |
25 ms |
6232 KB |
Output is correct |
92 |
Correct |
31 ms |
6236 KB |
Output is correct |
93 |
Correct |
3 ms |
4940 KB |
Output is correct |
94 |
Correct |
96 ms |
22904 KB |
Output is correct |
95 |
Correct |
88 ms |
22604 KB |
Output is correct |
96 |
Correct |
89 ms |
22048 KB |
Output is correct |
97 |
Correct |
95 ms |
23616 KB |
Output is correct |
98 |
Correct |
105 ms |
23364 KB |
Output is correct |
99 |
Correct |
95 ms |
13616 KB |
Output is correct |
100 |
Correct |
111 ms |
13640 KB |
Output is correct |
101 |
Correct |
102 ms |
13720 KB |
Output is correct |
102 |
Correct |
89 ms |
13988 KB |
Output is correct |
103 |
Correct |
81 ms |
17560 KB |
Output is correct |
104 |
Correct |
87 ms |
17852 KB |
Output is correct |
105 |
Correct |
92 ms |
17504 KB |
Output is correct |
106 |
Correct |
93 ms |
18580 KB |
Output is correct |
107 |
Correct |
91 ms |
18368 KB |
Output is correct |
108 |
Correct |
100 ms |
23672 KB |
Output is correct |
109 |
Correct |
105 ms |
23636 KB |
Output is correct |
110 |
Correct |
69 ms |
12992 KB |
Output is correct |
111 |
Correct |
65 ms |
13004 KB |
Output is correct |
112 |
Correct |
107 ms |
13520 KB |
Output is correct |
113 |
Correct |
94 ms |
13504 KB |
Output is correct |