#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
struct SegTree
{
int sz;
vector<int> st, lz;
void init(int n)
{
sz = 1;
while (sz < n) sz <<= 1;
st.assign(sz << 1, 0);
lz.assign(sz << 1, 0);
}
void relax(int l, int r, int x)
{
if (!lz[x]) return;
st[x] = r - l - st[x];
if (l + 1 == r)
{
lz[x] = 0;
return;
}
lz[2*x + 1] ^= 1, lz[2*x + 2] ^= 1;
}
void make(int l, int r, int x, int lx, int rx)
{
if (lx >= rx) return;
relax(l, r, x);
if (l >= rx || r <= lx) return;
if (l >= lx && r <= rx)
{
lz[x] ^= 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x + 1, lx, rx);
make(mid, r, 2*x + 2, lx, rx);
st[x] = st[2*x + 1] + st[2*x + 2];
}
int get(int l, int r, int x, int lx, int rx)
{
if (lx >= rx) return 0;
if (l >= rx || r <= lx) return 0;
relax(l, r, x);
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x + 1, lx, rx) + get(mid, r, 2*x + 2, lx, rx);
}
};
const int MXN = 1e5 + 5;
int n, q, r, SZ;
vector<int> adj[MXN];
int head[MXN], val[MXN], sz[MXN], dep[MXN], par[MXN];
int in[MXN], out[MXN], tim = -1;
SegTree st;
void _dfs(int a, int p)
{
sz[a] = 1;
vector<int> nw;
for (int v : adj[a])
{
if (v == p) continue;
_dfs(v, a);
nw.push_back(v);
sz[a] += sz[v];
}
swap(nw, adj[a]);
int mx = 0;
for (int i = 0; i < adj[a].size(); i++)
{
if (sz[adj[a][i]] > sz[adj[a][mx]]) mx = i;
}
if (!adj[a].empty()) swap(adj[a][0], adj[a][mx]);
}
void dfs(int a)
{
in[a] = ++tim;
for (int i = 0; i < adj[a].size(); i++)
{
if (!i) head[adj[a][i]] = head[a];
else head[adj[a][i]] = adj[a][i];
dep[adj[a][i]] = dep[a] + 1;
par[adj[a][i]] = a;
dfs(adj[a][i]);
}
out[a] = tim;
}
int ans = 0;
void upd(int u, int v)
{
while (head[u] != head[v])
{
if (dep[head[u]] < dep[head[v]]) swap(u, v);
if (head[u] == u)
{
ans -= val[in[u]];
val[in[u]] ^= 1;
ans += val[in[u]];
u = par[u];
}
else
{
st.make(0, SZ, 0, in[head[u]] + 1, in[u] + 1);
u = head[u];
}
}
if (dep[u] < dep[v]) swap(u, v);
st.make(0, SZ, 0, in[v] + 1, in[u] + 1);
}
int cntleaf = 0;
int add[MXN];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
{
if (adj[i].size() >= 2)
{
r = i;
break;
}
}
st.init(n);
SZ = st.sz;
_dfs(r, r);
head[r] = r;
dfs(r);
for (int i = 1; i <= n; i++)
{
cntleaf += adj[i].empty();
if (adj[i].empty()) upd(r, i);
}
for (int i = 1; i <= q; i++)
{
set<int> s;
int d;
cin >> d;
for (int j = 1; j <= d; j++)
{
int x;
cin >> x;
add[x] ^= 1;
s.insert(x);
}
int nw = cntleaf;
for (int j : s) nw -= adj[j].empty();
if ((nw + d) & 1)
{
for (int j : s) add[j] = 0;
cout << -1 << '\n';
continue;
}
for (int j : s)
{
if (adj[j].empty() && !add[j]) upd(r, j);
else if (!adj[j].empty() && add[j]) upd(r, j);
}
int all = st.get(0, SZ, 0, 0, n);
cout << (n - 1 - ans - all) * 2 + ans + all + d << '\n';
for (int j : s)
{
if (adj[j].empty() && !add[j]) upd(r, j);
else if (!adj[j].empty() && add[j]) upd(r, j);
}
for (int j : s) add[j] = 0;
}
}
Compilation message
cleaning.cpp: In function 'void _dfs(long long int, long long int)':
cleaning.cpp:78:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = 0; i < adj[a].size(); i++)
| ~~^~~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(long long int)':
cleaning.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < adj[a].size(); i++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
11400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
9560 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9620 KB |
Output is correct |
| 3 |
Correct |
28 ms |
17872 KB |
Output is correct |
| 4 |
Correct |
44 ms |
17544 KB |
Output is correct |
| 5 |
Correct |
55 ms |
18116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
15440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
11400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
