// author : HuuHung
// 25.3.2024
#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()
using namespace std;
void maxzi(int &a, int b){
a = max(a, b);
}
void minzi(int &a, int b){
a = min(a, b);
}
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int Pow(int a, int b){
if (b == 0) return 1;
if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
int c = Pow(a, b / 2);
return 1ll * c * c % mod;
}
// * end
int deg[N], num[N];
vector <int> s;
vector <int> nw[N];
struct LCA{
vi st, ed, _lg, high, type, num[2];
vector <vi> euler, adj;
int cnt, ans, root, leaf;
void dfs1(int u, int pa){
++ cnt;
st[u] = cnt;
euler[cnt].pb(u);
if (deg[u] == 1) type[u] = 1, leaf ++;
for (int v : adj[u]){
if (v == pa) continue;
high[v] = high[u] + 1;
dfs1(v, u);
euler[++ cnt].pb(u);
type[u] ^= type[v];
}
ed[u] = cnt;
}
int check(int u, int v) {
return st[u] <= st[v] && ed[v] <= ed[u];
}
int min_by_time(int u, int v) {
return (st[u] < st[v] ? u : v);
}
void added(int u, int v){
adj[u].pb(v);
adj[v].pb(u);
}
void resize(int n){
leaf = 0;
ans = n - 1;
st.resize(n + 3, 0);
ed.resize(n + 3, 0);
euler.resize(2 * n + 5);
high.resize(n + 3, 0);
type.resize(n + 3, 0);
num[0].resize(n + 3, 0);
num[1].resize(n + 3, 0);
adj.resize(n + 3);
_lg.resize(2 * n + 5);
for (int i = 0; i <= 2 * n; ++ i) _lg[i] = log2(i);
}
void dfs2(int u, int pa){
for (int v : adj[u]){
if (v == pa) continue;
num[0][v] = num[0][u];
num[1][v] = num[1][u];
num[type[v]][v] ++;
ans += (type[v] ^ 1);
dfs2(v, u);
}
}
void init(int r){
root = r;
cnt = 0;
high[r] = 1;
dfs1(r, 0);
for (int lg = 1; lg < 20; ++lg) {
for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
}
dfs2(r, 0);
}
int get(int u, int v) {
int L = min(st[u], st[v]);
int R = max(ed[u], ed[v]);
int lg = _lg[R - L + 1];
return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
}
int dist(int t, int u, int pa){ return num[t][u] - num[t][pa]; }
} tree;
int process(){
int ans = tree.ans;
sort(s.begin(), s.end(), [&](int u, int v){
return tree.st[u] < tree.st[v];
});
int m = s.size();
for (int i = 1; i < m; ++ i) s.push_back(tree.get(s[i], s[i - 1]));
s.pb(tree.root);
sort(s.begin(), s.end(), [&](int u, int v) {
return tree.st[u] < tree.st[v];
});
s.erase(unique(s.begin(), s.end()), s.end());
reverse(s.begin(), s.end());
vector <int> stk;
for (auto u : s){
while (stk.size() && tree.check(u, stk.back())) {
int v = stk.back();
stk.pop_back();
nw[u].push_back(v);
}
stk.push_back(u);
}
function <void (int, int)> dfs = [&](int u, int pa){
for (int v : nw[u]){
if (v == pa) continue;
dfs(v, u);
num[u] ^= num[v];
}
if (num[u]) ans += (-tree.dist(0, u, pa) + tree.dist(1, u, pa));
};
dfs(tree.root, tree.root);
for (int u : s) nw[u].clear();
return ans;
}
void solve(){
int n, q;
cin >> n >> q;
tree.resize(n);
int root = 1;
for (int i = 1, u, v; i < n; ++ i){
cin >> u >> v;
tree.added(u, v);
deg[u] ++;
deg[v] ++;
if (deg[u] > 1) root = u;
if (deg[v] > 1) root = v;
}
tree.init(root);
int r = 0;
for (int i = 1; i <= n; ++ i) if (deg[i] == 1) ++ r;
while (q --){
int ro = r;
for (int v : s) num[v] = 0;
s.clear();
vector <int> cur;
int d; cin >> d;
for (int i = 1; i <= d; ++ i){
int a; cin >> a;
if (!num[a]) cur.pb(a);
num[a] ++;
if (num[a] == 1 && deg[a] == 1) continue;
++ ro;
}
int kh = 0;
for (int v : cur){
num[v] %= 2;
if ((num[v] && deg[v] > 1) || (!num[v] && deg[v] == 1)) num[v] = 1, s.pb(v);
if (deg[v] == 1) kh ++;
}
//cout << kh << endl;
if (ro % 2) cout << -1 << '\n';
else cout << process() + d << '\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t --) solve();
return 0;
}
Compilation message
cleaning.cpp: In member function 'void LCA::init(int)':
cleaning.cpp:117:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
117 | euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
| ~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
11952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7000 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
106 ms |
44520 KB |
Output is correct |
| 4 |
Correct |
86 ms |
32428 KB |
Output is correct |
| 5 |
Correct |
109 ms |
45476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
11 ms |
7256 KB |
Output is correct |
| 3 |
Correct |
119 ms |
49140 KB |
Output is correct |
| 4 |
Correct |
124 ms |
47464 KB |
Output is correct |
| 5 |
Correct |
95 ms |
45108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
12616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
30240 KB |
Output is correct |
| 2 |
Incorrect |
103 ms |
30080 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
45844 KB |
Output is correct |
| 2 |
Correct |
140 ms |
49440 KB |
Output is correct |
| 3 |
Correct |
200 ms |
49168 KB |
Output is correct |
| 4 |
Correct |
149 ms |
48036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
11952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
