#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
using namespace std;
class SegmentTree
{
private:
// first = even, second = odd
vector<pii> tree;
vector<int> lazy;
int n;
void build(vector<pii> &arr, int v, int tl, int tr)
{
if (tl == tr)
tree[v] = arr[tl];
else
{
int m = (tl + tr) / 2;
build(arr, 2 * v, tl, m);
build(arr, 2 * v + 1, m + 1, tr);
tree[v].first = tree[2 * v].first + tree[2 * v + 1].first;
tree[v].second = tree[2 * v].second + tree[2 * v + 1].second;
}
}
pii _query(int l, int r, int v, int tl, int tr)
{
if (lazy[v] != 0)
{
if (lazy[v] & 1)
swap(tree[v].first, tree[v].second);
if (tl != tr)
{
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (r < tl || tr < l)
return {0, 0};
if (l <= tl && tr <= r)
return tree[v];
int m = (tl + tr) / 2;
pii lpi = _query(l, r, 2 * v, tl, m), rpi = _query(l, r, 2 * v + 1, m + 1, tr);
return {lpi.first + rpi.first, lpi.second + rpi.second};
}
void _update(int l, int r, int v, int tl, int tr)
{
if (lazy[v] != 0)
{
if (lazy[v] & 1)
swap(tree[v].first, tree[v].second);
if (tl != tr)
{
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
swap(tree[v].first, tree[v].second);
if (tl != tr)
{
lazy[2 * v]++;
lazy[2 * v + 1]++;
}
return;
}
int m = (tl + tr) / 2;
_update(l, r, 2 * v, tl, m);
_update(l, r, 2 * v + 1, m + 1, tr);
tree[v].first = tree[2 * v].first + tree[2 * v + 1].first;
tree[v].second = tree[2 * v].second + tree[2 * v + 1].second;
}
public:
SegmentTree() {}
void resize(vector<pii> &arr)
{
n = arr.size();
tree.resize(4 * n);
lazy.resize(4 * n, 0);
build(arr, 1, 0, n - 1);
}
pii query(int l, int r)
{
if (l > r)
swap(l, r);
return _query(l, r, 1, 0, n - 1);
}
void update(int l, int r)
{
if (l > r)
swap(l, r);
return _update(l, r, 1, 0, n - 1);
}
};
vector<vector<int>> graph;
vector<int> sz, leaf_cnt, label, depth, top, par;
SegmentTree tree;
int init_hld(int v, int p)
{
sz[v] = 1;
if (graph[v].size() == 1)
leaf_cnt[v] = 1;
for (int i = 0; i < graph[v].size(); i++)
{
int u = graph[v][i];
if (u == p)
continue;
depth[u] = 1 + depth[v];
par[u] = v;
sz[v] += init_hld(u, v);
leaf_cnt[v] += leaf_cnt[u];
if (sz[u] > sz[graph[v][0]])
swap(graph[v][0], graph[v][i]);
}
return sz[v];
}
void label_hld(int v, int p, int tp, int &id)
{
label[v] = id++;
top[v] = tp;
for (int i = 0; i < graph[v].size(); i++)
{
int u = graph[v][i];
if (u == p)
continue;
label_hld(u, v, (i == 0 ? tp : u), id);
}
}
int hld_lca(int a, int b)
{
while (top[a] != top[b])
{
if (depth[top[a]] > depth[top[b]])
a = par[top[a]];
else
b = par[top[b]];
}
return depth[a] < depth[b] ? a : b;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
graph.resize(n);
sz.resize(n);
leaf_cnt.resize(n, 0);
label.resize(n);
depth.resize(n, 0);
top.resize(n, 0);
par.resize(n, 0);
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
graph[--a].push_back(--b);
graph[b].push_back(a);
}
init_hld(0, -1);
int id = 0;
label_hld(0, -1, 0, id);
vector<pii> init_seg(id);
for (int i = 0; i < n; i++)
init_seg[label[i]] = {!(leaf_cnt[i] & 1), leaf_cnt[i] & 1};
tree.resize(init_seg);
while (q--)
{
vector<bool> leafs(n, 0);
int leaf_sol = 0, curr_lfs = leaf_cnt[0];
vector<pii> upd_res;
int di;
cin >> di;
for (int i = 0; i < di; i++)
{
int x;
cin >> x;
--x;
if (graph[x].size() == 1)
{
leaf_sol++;
if (leafs[x])
curr_lfs++;
else
leafs[x] = true;
continue;
}
// otherwise we have to heavylight
curr_lfs++;
leaf_sol++;
while (x != 0)
{
tree.update(label[top[x]], label[x]);
upd_res.push_back({label[top[x]], label[x]});
x = par[top[x]];
}
}
if (curr_lfs % 2 == 1)
cout << -1 << endl;
else
{
pii sol = tree.query(1, id - 1);
cout << 2 * sol.first + sol.second + leaf_sol << endl;
}
// now we restore
for (pii &p : upd_res)
tree.update(p.first, p.second);
}
}
Compilation message
cleaning.cpp: In function 'int init_hld(int, int)':
cleaning.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < graph[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
cleaning.cpp: In function 'void label_hld(int, int, int, int&)':
cleaning.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int i = 0; i < graph[v].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
4020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
3196 KB |
Output is correct |
| 2 |
Correct |
41 ms |
3028 KB |
Output is correct |
| 3 |
Correct |
38 ms |
22352 KB |
Output is correct |
| 4 |
Correct |
100 ms |
21960 KB |
Output is correct |
| 5 |
Correct |
35 ms |
20308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
10564 KB |
Output is correct |
| 2 |
Incorrect |
189 ms |
10716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
16236 KB |
Output is correct |
| 2 |
Correct |
102 ms |
18880 KB |
Output is correct |
| 3 |
Correct |
151 ms |
18200 KB |
Output is correct |
| 4 |
Correct |
134 ms |
19300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
4020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
