#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( 1, 0 );
decomp( 1, 0, 1 );
}
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 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;
}
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 |
1 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
107 ms |
8240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
7140 KB |
Output is correct |
| 2 |
Correct |
78 ms |
7172 KB |
Output is correct |
| 3 |
Correct |
63 ms |
13516 KB |
Output is correct |
| 4 |
Correct |
108 ms |
11980 KB |
Output is correct |
| 5 |
Correct |
123 ms |
14028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
9296 KB |
Output is correct |
| 2 |
Correct |
88 ms |
8984 KB |
Output is correct |
| 3 |
Correct |
98 ms |
45648 KB |
Output is correct |
| 4 |
Correct |
195 ms |
42580 KB |
Output is correct |
| 5 |
Correct |
104 ms |
42520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
319 ms |
11268 KB |
Output is correct |
| 2 |
Correct |
301 ms |
11364 KB |
Output is correct |
| 3 |
Correct |
251 ms |
9308 KB |
Output is correct |
| 4 |
Correct |
323 ms |
11724 KB |
Output is correct |
| 5 |
Correct |
289 ms |
11104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
410 ms |
14028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
107 ms |
8240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
