#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;
int n, q;
struct SegmentTree
{
struct Node
{
int cntODD;
int cntEVEN;
bool lazy;
Node()
{
cntODD = 0;
cntEVEN = 0;
lazy = false;
}
};
Node tree[4*MAXN];
Node combine(Node left, Node right)
{
Node res;
res.cntODD = left.cntODD + right.cntODD;
res.cntEVEN = left.cntEVEN + right.cntEVEN;
return res;
}
void push(int node, int l, int r)
{
if (!tree[node].lazy)
{
return;
}
std::swap(tree[node].cntODD, tree[node].cntEVEN);
if (l < r)
{
tree[2*node].lazy ^= 1;
tree[2*node + 1].lazy ^= 1;
}
tree[node].lazy = false;
}
void build(int l, int r, int node, std::vector <int> tour, bool par[])
{
if (l == r)
{
if (par[tour[l]]) tree[node].cntODD = 1;
else tree[node].cntEVEN = 1;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node, tour, par);
build(mid + 1, r, 2*node + 1, tour, par);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryL, int queryR)
{
push(node, l, r);
if (r < queryL || queryR < l)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy ^= 1;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
update(l, mid, 2*node, queryL, queryR);
update(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
int count()
{
return tree[1].cntEVEN;
}
void build(std::vector <int> tour, bool par[])
{
assert(tour.size() == n);
build(0, n - 1, 1, tour, par);
}
void update(int l, int r)
{
update(0, n - 1, 1, l, r);
}
};
int cnt;
int par[MAXN];
bool res[MAXN];
bool was[MAXN];
SegmentTree tree;
bool isLeaf[MAXN];
std::vector <int> g[MAXN];
std::vector <int> tour;
int segPos[MAXN];
int heavy[MAXN];
int head[MAXN];
int sz[MAXN];
int dfs(int node, int p)
{
par[node] = p;
if (g[node].size() == 1)
{
cnt ^= 1;
isLeaf[node] = true;
res[node] = 1;
return res[node];
}
res[node] = 0;
for (const int &u : g[node])
{
if (u == p)
{
continue;
}
res[node] ^= dfs(u, node);
}
return res[node];
}
void initDFS(int node)
{
sz[node] = 1;
heavy[node] = 0;
for (const int &u : g[node])
{
if (u == par[node])
{
continue;
}
initDFS(u);
sz[node] += sz[u];
if (sz[u] > sz[heavy[node]])
{
heavy[node] = u;
}
}
}
void buildTour(int node, int h)
{
head[node] = h;
tour.push_back(node);
segPos[node] = tour.size() - 1;
if (heavy[node] != 0)
{
buildTour(heavy[node], h);
}
for (const int &u : g[node])
{
if (u == par[node] || u == heavy[node])
{
continue;
}
buildTour(u, u);
}
}
int myLog;
void climb(int node)
{
myLog++;
tree.update(segPos[head[node]], segPos[node]);
if (par[head[node]] != 0)
{
climb(par[head[node]]);
} else
{
cnt ^= 1;
}
}
int a[MAXN];
void solve()
{
int root = 1;
if (g[1].size() == 1) root = g[1][0];
dfs(root, 0);
initDFS(root);
buildTour(root, root);
tree.build(tour, res);
for (int i = 1 ; i <= q ; ++i)
{
int d;
std::cin >> d;
for (int j = 1 ; j <= d ; ++j)
{
std::cin >> a[j];
if (isLeaf[a[j]] && !was[a[j]]) was[a[j]] = true;
else
{
myLog = 0;
climb(a[j]);
assert(myLog < 20);
}
}
if (cnt) std::cout << -1 << '\n';
else std::cout << n + d + tree.count() - 2 << '\n';
for (int j = 1 ; j <= d ; ++j)
{
if (isLeaf[a[j]] && was[a[j]]) was[a[j]] = false;
else
{
myLog = 0;
climb(a[j]);
assert(myLog < 20);
}
}
}
}
void input()
{
std::cin >> n >> q;
for (int i = 2 ; i <= n ; ++i)
{
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from cleaning.cpp:4:
cleaning.cpp: In member function 'void SegmentTree::build(std::vector<int>, bool*)':
cleaning.cpp:100:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
100 | assert(tour.size() == n);
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
532 ms |
21064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
19372 KB |
Output is correct |
| 2 |
Correct |
44 ms |
19240 KB |
Output is correct |
| 3 |
Execution timed out |
1050 ms |
31376 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
19724 KB |
Output is correct |
| 2 |
Correct |
53 ms |
19728 KB |
Output is correct |
| 3 |
Execution timed out |
1018 ms |
36868 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
521 ms |
21688 KB |
Output is correct |
| 2 |
Correct |
494 ms |
21504 KB |
Output is correct |
| 3 |
Correct |
466 ms |
21068 KB |
Output is correct |
| 4 |
Correct |
458 ms |
21476 KB |
Output is correct |
| 5 |
Correct |
480 ms |
21708 KB |
Output is correct |
| 6 |
Correct |
489 ms |
21392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
26368 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
30996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
532 ms |
21064 KB |
Output is correct |
| 3 |
Correct |
46 ms |
19372 KB |
Output is correct |
| 4 |
Correct |
44 ms |
19240 KB |
Output is correct |
| 5 |
Execution timed out |
1050 ms |
31376 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
