#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
const int undef = 0;
int leafs[MAX_N + 1], parent[MAX_N + 1], children[MAX_N + 1], a[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int ans;
void dfs( int u, int p ) {
parent[u] = p;
for ( int v: adj[u] ) {
if ( v == p )
continue;
children[u]++;
dfs( v, u );
leafs[u] += leafs[v];
}
leafs[u] += (children[u] == 0);
ans += 2 - leafs[u] % 2;
}
struct info {
int nr0, nr1;
info operator + ( info x ) {
return { nr0 + x.nr0, nr1 + x.nr1 };
}
};
struct SegTree {
info segTree[4 * MAX_N];
bool lazy[4 * MAX_N];
void init( int v, int l, int r ) {
lazy[v] = 0;
if ( l == r ) {
segTree[v] = { 1, 0 };
return;
}
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid );
init( v * 2 + 2, mid + 1, r );
segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
}
void propag( int v, int l, int r ) {
if ( lazy[v] == 0 )
return;
swap( segTree[v].nr0, segTree[v].nr1 );
if ( l != r ) {
lazy[v * 2 + 1] ^= 1;
lazy[v * 2 + 2] ^= 1;
}
lazy[v] = 0;
}
void update( int v, int l, int r, int lu, int ru ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] ^= 1;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru );
update( v * 2 + 2, mid + 1, r, lu, ru );
segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
}
info query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return { 0, 0 };
if ( lq <= l && r <= rq )
return segTree[v];
int mid = (l + r) / 2;
return query( v * 2 + 1, l, mid, lq, rq ) + query( v * 2 + 2, mid + 1, r, lq, rq );
}
};
struct HPD {
int n, r, curPos;
int sz[MAX_N], parent[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[MAX_N], rightPos[MAX_N];
SegTree aint;
void dfs( int u, int p ) {
int maxSz = -1;
parent[u] = p;
depth[u] = depth[p] + 1;
sz[u] = 1;
heavy[u] = undef;
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfs( v, u );
sz[u] += sz[v];
if ( sz[v] > maxSz ) {
maxSz = sz[v];
heavy[u] = v;
}
}
}
void decomp( int u, int p, int h ) {
head[u] = h;
leftPos[u] = ++curPos;
if ( heavy[u] != undef )
decomp( heavy[u], u, h );
for ( int v: adj[u] ) {
if ( v == p || v == heavy[u] )
continue;
decomp( v, u, v );
}
rightPos[u] = curPos;
}
void init( int _n, int _r ) {
n = _n;
r = _r;
aint.init( 0, 1, n );
dfs( r, 0 );
decomp( r, 0, r );
}
void updatePath( int u, int v ) {
while ( head[u] != head[v] ) {
if ( depth[head[u]] < depth[head[v]] )
swap( u, v );
aint.update( 0, 1, n, leftPos[head[u]], leftPos[u] );
u = parent[head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
aint.update( 0, 1, n, leftPos[u], leftPos[v] );
}
info queryPath( int u, int v ) {
info ans = { 0, 0 };
while ( head[u] != head[v] ) {
if ( depth[head[u]] < depth[head[v]] )
swap( u, v );
ans = ans + aint.query( 0, 1, n, leftPos[head[u]], leftPos[u] );
u = parent[head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
ans = ans + aint.query( 0, 1, n, leftPos[u], leftPos[v] );
return ans;
}
} arb;
int main() {
int n, q;
cin >> n >> q;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
int r = 1;
while ( adj[r].size() == 1 )
r++;
ans = 0;
dfs( r, 0 );
arb.init( n, r );
for ( int v = 1; v <= n; v++ ) {
if ( leafs[v] % 2 == 1 )
arb.updatePath( v, v );
}
for ( int i = 0; i < q; i++ ) {
int d;
int lf = 0, change = 0;
cin >> d;
for ( int i = 0; i < d; i++ ) {
cin >> a[i];
int v = a[i];
change++;
if ( children[v] == 0 ) {
children[v]++;
continue;
}
/*while ( v != 0 ) {
change -= 2 - leafs[v] % 2;
leafs[v]++;
change += 2 - leafs[v] % 2;
v = parent[v];
}*/
lf++;
info x;
x = arb.queryPath( v, r );
change -= x.nr0 * 2 + x.nr1;
arb.updatePath( v, r );
x = arb.queryPath( v, r );
change += x.nr0 * 2 + x.nr1;
}
info x = arb.queryPath( r, r );
change -= x.nr0 * 2 + x.nr1;
cout << (arb.queryPath( r, r ).nr0 == 1 ? ans + change : -1) << "\n";
for ( int i = 0; i < d; i++ ) {
int v = a[i];
if ( children[v] == 1 ) {
children[v]--;
continue;
}
arb.updatePath( v, r );
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
107 ms |
10580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
9932 KB |
Output is correct |
| 2 |
Correct |
79 ms |
9644 KB |
Output is correct |
| 3 |
Correct |
64 ms |
14540 KB |
Output is correct |
| 4 |
Correct |
109 ms |
13516 KB |
Output is correct |
| 5 |
Correct |
159 ms |
15132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
11344 KB |
Output is correct |
| 2 |
Correct |
65 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
102 ms |
46924 KB |
Output is correct |
| 4 |
Correct |
165 ms |
44228 KB |
Output is correct |
| 5 |
Correct |
86 ms |
43460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
13404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
13392 KB |
Output is correct |
| 2 |
Correct |
290 ms |
13232 KB |
Output is correct |
| 3 |
Correct |
246 ms |
11316 KB |
Output is correct |
| 4 |
Correct |
300 ms |
13140 KB |
Output is correct |
| 5 |
Correct |
290 ms |
13152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
424 ms |
16208 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 |
107 ms |
10580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
