#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Tran The Bao - ghostwriter
Training for VOI23 gold medal
----------------------------------------------------------------
DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
const int N = 1e5 + 1;
int n, m, k, tin[N], pe[N], s[N], h[N], p[N][17], timer = 0;
pi e[N];
vi adj[N], ans;
bool cmp(const int &a, const int &b) { return tin[a] < tin[b]; }
int lca(int a, int b) {
if (h[a] > h[b]) swap(a, b);
int diff = h[b] - h[a];
FOR(i, 0, 16)
if (diff & (1 << i))
b = p[b][i];
if (a == b) return a;
FOS(i, 16, 0)
if (p[a][i] != p[b][i]) {
a = p[a][i];
b = p[b][i];
}
return p[a][0];
}
void dfs(int u, int p) {
tin[u] = ++timer;
::p[u][0] = p;
FOR(i, 1, 16) ::p[u][i] = ::p[::p[u][i - 1]][i - 1];
EACH(j, adj[u]) {
int v = (e[j].st == u? e[j].nd : e[j].st);
if (v == p) continue;
pe[v] = j;
h[v] = h[u] + 1;
dfs(v, u);
}
}
void dfs1(int u, int p) {
EACH(j, adj[u]) {
int v = (e[j].st == u? e[j].nd : e[j].st);
if (v == p) continue;
dfs1(v, u);
s[u] += s[v];
}
if (s[u] >= k && pe[u]) ans.pb(pe[u]);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> m >> k;
FOR(i, 1, n - 1) {
int a, b;
cin >> a >> b;
e[i] = {a, b};
adj[a].pb(i);
adj[b].pb(i);
}
dfs(1, 0);
FOR(i, 1, m) {
int s;
cin >> s;
vi a(s);
EACH(j, a) cin >> j;
sort(all(a), cmp);
int LCA = a[0], prev = a[0];
FOR(j, 1, s - 1) {
int nLCA = lca(prev, a[j]);
++::s[a[j]];
--::s[nLCA];
if (h[nLCA] < h[LCA]) {
++::s[LCA];
--::s[nLCA];
LCA = nLCA;
}
prev = a[j];
}
}
dfs1(1, 0);
sort(all(ans));
cout << sz(ans) << '\n';
EACH(i, ans) cout << i << ' ';
return 0;
}
/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
----------------------------------------------------------------
From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/
Compilation message
railway.cpp: In function 'int lca(int, int)':
railway.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
railway.cpp:59:2: note: in expansion of macro 'FOR'
59 | FOR(i, 0, 16)
| ^~~
railway.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
railway.cpp:63:2: note: in expansion of macro 'FOS'
63 | FOS(i, 16, 0)
| ^~~
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
railway.cpp:73:2: note: in expansion of macro 'FOR'
73 | FOR(i, 1, 16) ::p[u][i] = ::p[::p[u][i - 1]][i - 1];
| ^~~
railway.cpp:36:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define EACH(i, x) for (auto &(i) : (x))
| ^
railway.cpp:74:2: note: in expansion of macro 'EACH'
74 | EACH(j, adj[u]) {
| ^~~~
railway.cpp: In function 'void dfs1(int, int)':
railway.cpp:36:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define EACH(i, x) for (auto &(i) : (x))
| ^
railway.cpp:83:2: note: in expansion of macro 'EACH'
83 | EACH(j, adj[u]) {
| ^~~~
railway.cpp: In function 'int main()':
railway.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
railway.cpp:96:5: note: in expansion of macro 'FOR'
96 | FOR(i, 1, n - 1) {
| ^~~
railway.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
railway.cpp:104:5: note: in expansion of macro 'FOR'
104 | FOR(i, 1, m) {
| ^~~
railway.cpp:36:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define EACH(i, x) for (auto &(i) : (x))
| ^
railway.cpp:108:6: note: in expansion of macro 'EACH'
108 | EACH(j, a) cin >> j;
| ^~~~
railway.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
railway.cpp:111:6: note: in expansion of macro 'FOR'
111 | FOR(j, 1, s - 1) {
| ^~~
railway.cpp:36:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define EACH(i, x) for (auto &(i) : (x))
| ^
railway.cpp:126:5: note: in expansion of macro 'EACH'
126 | EACH(i, ans) cout << i << ' ';
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
6 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3980 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4436 KB |
Output is correct |
7 |
Correct |
6 ms |
4116 KB |
Output is correct |
8 |
Correct |
6 ms |
4052 KB |
Output is correct |
9 |
Correct |
5 ms |
4060 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2684 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
6 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3980 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4436 KB |
Output is correct |
7 |
Correct |
6 ms |
4116 KB |
Output is correct |
8 |
Correct |
6 ms |
4052 KB |
Output is correct |
9 |
Correct |
5 ms |
4060 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2684 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2692 KB |
Output is correct |
15 |
Correct |
20 ms |
4300 KB |
Output is correct |
16 |
Correct |
19 ms |
4436 KB |
Output is correct |
17 |
Correct |
20 ms |
4388 KB |
Output is correct |
18 |
Correct |
6 ms |
4364 KB |
Output is correct |
19 |
Correct |
6 ms |
4112 KB |
Output is correct |
20 |
Correct |
21 ms |
4512 KB |
Output is correct |
21 |
Correct |
20 ms |
4464 KB |
Output is correct |
22 |
Correct |
2 ms |
2640 KB |
Output is correct |
23 |
Correct |
7 ms |
3964 KB |
Output is correct |
24 |
Correct |
7 ms |
3924 KB |
Output is correct |
25 |
Correct |
2 ms |
2772 KB |
Output is correct |
26 |
Correct |
2 ms |
2684 KB |
Output is correct |
27 |
Correct |
6 ms |
4436 KB |
Output is correct |
28 |
Correct |
6 ms |
4108 KB |
Output is correct |
29 |
Correct |
5 ms |
3980 KB |
Output is correct |
30 |
Correct |
5 ms |
4052 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2688 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
25260 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
80 ms |
23596 KB |
Output is correct |
4 |
Correct |
91 ms |
23140 KB |
Output is correct |
5 |
Correct |
87 ms |
24000 KB |
Output is correct |
6 |
Correct |
75 ms |
24152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
20428 KB |
Output is correct |
2 |
Correct |
95 ms |
15664 KB |
Output is correct |
3 |
Correct |
95 ms |
15236 KB |
Output is correct |
4 |
Correct |
104 ms |
15188 KB |
Output is correct |
5 |
Correct |
81 ms |
15240 KB |
Output is correct |
6 |
Correct |
67 ms |
19212 KB |
Output is correct |
7 |
Correct |
72 ms |
19104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
20428 KB |
Output is correct |
2 |
Correct |
95 ms |
15664 KB |
Output is correct |
3 |
Correct |
95 ms |
15236 KB |
Output is correct |
4 |
Correct |
104 ms |
15188 KB |
Output is correct |
5 |
Correct |
81 ms |
15240 KB |
Output is correct |
6 |
Correct |
67 ms |
19212 KB |
Output is correct |
7 |
Correct |
72 ms |
19104 KB |
Output is correct |
8 |
Correct |
81 ms |
19224 KB |
Output is correct |
9 |
Correct |
98 ms |
19284 KB |
Output is correct |
10 |
Correct |
79 ms |
24060 KB |
Output is correct |
11 |
Correct |
73 ms |
23984 KB |
Output is correct |
12 |
Correct |
65 ms |
15496 KB |
Output is correct |
13 |
Correct |
73 ms |
15580 KB |
Output is correct |
14 |
Correct |
91 ms |
15252 KB |
Output is correct |
15 |
Correct |
93 ms |
15212 KB |
Output is correct |
16 |
Correct |
87 ms |
15164 KB |
Output is correct |
17 |
Correct |
90 ms |
15244 KB |
Output is correct |
18 |
Correct |
99 ms |
15204 KB |
Output is correct |
19 |
Correct |
84 ms |
15656 KB |
Output is correct |
20 |
Correct |
70 ms |
19432 KB |
Output is correct |
21 |
Correct |
72 ms |
19508 KB |
Output is correct |
22 |
Correct |
70 ms |
19528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
6 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3980 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4436 KB |
Output is correct |
7 |
Correct |
6 ms |
4116 KB |
Output is correct |
8 |
Correct |
6 ms |
4052 KB |
Output is correct |
9 |
Correct |
5 ms |
4060 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2684 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2692 KB |
Output is correct |
15 |
Correct |
20 ms |
4300 KB |
Output is correct |
16 |
Correct |
19 ms |
4436 KB |
Output is correct |
17 |
Correct |
20 ms |
4388 KB |
Output is correct |
18 |
Correct |
6 ms |
4364 KB |
Output is correct |
19 |
Correct |
6 ms |
4112 KB |
Output is correct |
20 |
Correct |
21 ms |
4512 KB |
Output is correct |
21 |
Correct |
20 ms |
4464 KB |
Output is correct |
22 |
Correct |
2 ms |
2640 KB |
Output is correct |
23 |
Correct |
7 ms |
3964 KB |
Output is correct |
24 |
Correct |
7 ms |
3924 KB |
Output is correct |
25 |
Correct |
2 ms |
2772 KB |
Output is correct |
26 |
Correct |
2 ms |
2684 KB |
Output is correct |
27 |
Correct |
6 ms |
4436 KB |
Output is correct |
28 |
Correct |
6 ms |
4108 KB |
Output is correct |
29 |
Correct |
5 ms |
3980 KB |
Output is correct |
30 |
Correct |
5 ms |
4052 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2688 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
86 ms |
25260 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
80 ms |
23596 KB |
Output is correct |
39 |
Correct |
91 ms |
23140 KB |
Output is correct |
40 |
Correct |
87 ms |
24000 KB |
Output is correct |
41 |
Correct |
75 ms |
24152 KB |
Output is correct |
42 |
Correct |
73 ms |
20428 KB |
Output is correct |
43 |
Correct |
95 ms |
15664 KB |
Output is correct |
44 |
Correct |
95 ms |
15236 KB |
Output is correct |
45 |
Correct |
104 ms |
15188 KB |
Output is correct |
46 |
Correct |
81 ms |
15240 KB |
Output is correct |
47 |
Correct |
67 ms |
19212 KB |
Output is correct |
48 |
Correct |
72 ms |
19104 KB |
Output is correct |
49 |
Correct |
81 ms |
19224 KB |
Output is correct |
50 |
Correct |
98 ms |
19284 KB |
Output is correct |
51 |
Correct |
79 ms |
24060 KB |
Output is correct |
52 |
Correct |
73 ms |
23984 KB |
Output is correct |
53 |
Correct |
65 ms |
15496 KB |
Output is correct |
54 |
Correct |
73 ms |
15580 KB |
Output is correct |
55 |
Correct |
91 ms |
15252 KB |
Output is correct |
56 |
Correct |
93 ms |
15212 KB |
Output is correct |
57 |
Correct |
87 ms |
15164 KB |
Output is correct |
58 |
Correct |
90 ms |
15244 KB |
Output is correct |
59 |
Correct |
99 ms |
15204 KB |
Output is correct |
60 |
Correct |
84 ms |
15656 KB |
Output is correct |
61 |
Correct |
70 ms |
19432 KB |
Output is correct |
62 |
Correct |
72 ms |
19508 KB |
Output is correct |
63 |
Correct |
70 ms |
19528 KB |
Output is correct |
64 |
Correct |
74 ms |
19388 KB |
Output is correct |
65 |
Correct |
103 ms |
15248 KB |
Output is correct |
66 |
Correct |
97 ms |
15384 KB |
Output is correct |
67 |
Correct |
104 ms |
15184 KB |
Output is correct |
68 |
Correct |
79 ms |
15672 KB |
Output is correct |
69 |
Correct |
64 ms |
15580 KB |
Output is correct |
70 |
Correct |
97 ms |
19620 KB |
Output is correct |
71 |
Correct |
82 ms |
19084 KB |
Output is correct |
72 |
Correct |
2 ms |
2680 KB |
Output is correct |
73 |
Correct |
7 ms |
3924 KB |
Output is correct |
74 |
Correct |
6 ms |
3924 KB |
Output is correct |
75 |
Correct |
2 ms |
2688 KB |
Output is correct |
76 |
Correct |
2 ms |
2688 KB |
Output is correct |
77 |
Correct |
8 ms |
4480 KB |
Output is correct |
78 |
Correct |
6 ms |
4052 KB |
Output is correct |
79 |
Correct |
5 ms |
3976 KB |
Output is correct |
80 |
Correct |
6 ms |
4052 KB |
Output is correct |
81 |
Correct |
2 ms |
2644 KB |
Output is correct |
82 |
Correct |
2 ms |
2688 KB |
Output is correct |
83 |
Correct |
2 ms |
2644 KB |
Output is correct |
84 |
Correct |
2 ms |
2688 KB |
Output is correct |
85 |
Correct |
2 ms |
2692 KB |
Output is correct |
86 |
Correct |
24 ms |
4296 KB |
Output is correct |
87 |
Correct |
21 ms |
4308 KB |
Output is correct |
88 |
Correct |
23 ms |
4296 KB |
Output is correct |
89 |
Correct |
7 ms |
4364 KB |
Output is correct |
90 |
Correct |
9 ms |
4120 KB |
Output is correct |
91 |
Correct |
20 ms |
4364 KB |
Output is correct |
92 |
Correct |
21 ms |
4228 KB |
Output is correct |
93 |
Correct |
2 ms |
2644 KB |
Output is correct |
94 |
Correct |
95 ms |
23944 KB |
Output is correct |
95 |
Correct |
86 ms |
23572 KB |
Output is correct |
96 |
Correct |
84 ms |
22952 KB |
Output is correct |
97 |
Correct |
101 ms |
23932 KB |
Output is correct |
98 |
Correct |
86 ms |
23980 KB |
Output is correct |
99 |
Correct |
95 ms |
15336 KB |
Output is correct |
100 |
Correct |
113 ms |
15360 KB |
Output is correct |
101 |
Correct |
114 ms |
15188 KB |
Output is correct |
102 |
Correct |
91 ms |
15568 KB |
Output is correct |
103 |
Correct |
89 ms |
19148 KB |
Output is correct |
104 |
Correct |
79 ms |
19468 KB |
Output is correct |
105 |
Correct |
72 ms |
19156 KB |
Output is correct |
106 |
Correct |
78 ms |
19420 KB |
Output is correct |
107 |
Correct |
82 ms |
19220 KB |
Output is correct |
108 |
Correct |
91 ms |
24004 KB |
Output is correct |
109 |
Correct |
84 ms |
23984 KB |
Output is correct |
110 |
Correct |
72 ms |
15572 KB |
Output is correct |
111 |
Correct |
61 ms |
15560 KB |
Output is correct |
112 |
Correct |
99 ms |
15284 KB |
Output is correct |
113 |
Correct |
106 ms |
15288 KB |
Output is correct |