#include<bits/stdc++.h>
using namespace std;
const int MX=100010;
int sz[MX], dep[MX], par[MX], top[MX], in[MX], n, q, i, j, k, a, b, ans, r, cnt, seg[4*MX], lazy[4*MX], A[MX], sz2[MX], x;
vector<int>w[MX], adj[MX];
void busy(int id, int s, int e, int m)
{
if(lazy[id])
{
seg[id*2]=(m-s+1)-seg[id*2];
seg[id*2+1]=(e-m)-seg[id*2+1];
lazy[id*2]^=1;
lazy[id*2+1]^=1;
}
}
void update(int id, int s, int e, int l, int r)
{
if(e<l||r<s)return;
if(l<=s&&e<=r)
{
seg[id]=(e-s+1)-seg[id];
lazy[id]^=1;
return;
}
int m=s+e>>1;
busy(id, s, e, m);
update(id*2, s, m, l, r);
update(id*2+1, m+1, e, l, r);
seg[id]=seg[id*2]+seg[id*2+1];
}
void dfs(int v, int P)
{
par[v]=P;
for(int i=0;i<w[v].size();i++)
{
int p=w[v][i];
if(p==P)continue;
adj[v].push_back(p);
dfs(p, v);
}
}
void dfs1(int v, int depth)
{
dep[v]=depth;
sz[v]=1;
for(int i=0;i<adj[v].size();i++)
{
int p=adj[v][i];
dfs1(p, depth+1);
sz[v]+=sz[p];
if(sz[p]>sz[adj[v][0]])
{
swap(adj[v][i], adj[v][0]);
}
}
}
void dfs2(int v)
{
in[v]=++cnt;
if(adj[v].size()==0)
{
sz2[v]=1;
return;
}
for(int i=0;i<adj[v].size();i++)
{
int p=adj[v][i];
top[p]=(i==0?top[v]:p);
dfs2(p);
sz2[v]+=sz2[p];
}
sz2[v]%=2;
}
void upd(int a, int b)
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a, b);
update(1, 1, n, in[top[a]], in[a]);
a=par[top[a]];
}
if(dep[a]>dep[b])swap(a, b);
update(1, 1, n, in[a], in[b]);
}
int main()
{
for(scanf("%d %d", &n, &q);++i<n;)
{
scanf("%d %d", &a, &b);
w[a].push_back(b);
w[b].push_back(a);
}
ans=n-2;
for(i=0;i++<n;)
{
if(w[i].size()>1)
{
r=i;
break;
}
}
top[r]=r;
dfs(r, 0);
dfs1(r, 1);
dfs2(r);
for(i=0;i++<n;)
{
A[i]=adj[i].size();
if(sz2[i]==0)ans++;
else
{
update(1, 1, n, in[i], in[i]);
}
}
x=sz2[r];
int aans=ans;
while(q--)
{
vector<int>v;
scanf("%d", &a);
while(a--)
{
scanf("%d", &b);
v.push_back(b);
A[b]++;
ans++;
if(A[b]==1)continue;
ans+=seg[1];
upd(r, b);
ans-=seg[1];
x=1-x;
}
if(x==0)printf("%d\n", ans);
else puts("-1");
for(i=v.size()-1;i>=0;i--)
{
b=v[i];
A[b]--;
ans--;
if(A[b]==0)continue;
ans+=seg[1];
upd(r, b);
ans-=seg[1];
x=1-x;
}
if(aans!=ans)for(i=0;;i++);
}
}
Compilation message
cleaning.cpp: In function 'void update(int, int, int, int, int)':
cleaning.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int m=s+e>>1;
| ~^~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<w[v].size();i++)
| ~^~~~~~~~~~~~
cleaning.cpp: In function 'void dfs1(int, int)':
cleaning.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<adj[v].size();i++)
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs2(int)':
cleaning.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<adj[v].size();i++)
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | for(scanf("%d %d", &n, &q);++i<n;)
| ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
cleaning.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%d", &b);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5112 KB |
Output is correct |
| 2 |
Execution timed out |
1077 ms |
7020 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
6012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
6652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
7788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
11372 KB |
Output is correct |
| 2 |
Execution timed out |
1083 ms |
10732 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
313 ms |
15300 KB |
Output is correct |
| 2 |
Correct |
179 ms |
17772 KB |
Output is correct |
| 3 |
Correct |
239 ms |
18796 KB |
Output is correct |
| 4 |
Correct |
230 ms |
18156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5112 KB |
Output is correct |
| 2 |
Execution timed out |
1077 ms |
7020 KB |
Time limit exceeded |
