#include <bits/stdc++.h>
using namespace std;
const int s=131072;
int seg[s*2];
int lazy[s*2];
void propagate(int node,int nodel,int noder) {
if (lazy[node]) {
seg[node]=noder-nodel+1-seg[node];
if (node<s) {
lazy[node*2]^=1;
lazy[node*2+1]^=1;
}
lazy[node]=0;
}
}
int sum(int l,int r,int node=1,int nodel=0,int noder=s-1) {
propagate(node,nodel,noder);
if (r<nodel||l>noder) {
return 0;
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}
void update(int l,int r,int node=1,int nodel=0,int noder=s-1) {
propagate(node,nodel,noder);
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
lazy[node]^=1;
propagate(node,nodel,noder);
return;
}
int mid=(nodel+noder)/2;
update(l,r,node*2,nodel,mid);
update(l,r,node*2+1,mid+1,noder);
seg[node]=seg[node*2]+seg[node*2+1];
}
int deg[100000];
vector<int> adj[100000];
vector<int> son[100000];
int leaf[100000];
int p[100000];
int dp[100000];
const int nn=-1e9;
int ind[100000];
int f=0;
int sz[100000];
int rev[100000];
int cnt[100000];
int psum[100001];
int top[100000];
int getleaf(int v) {
if (leaf[v]!=-1) {
return leaf[v];
}
if (son[v].empty()) {
return leaf[v]=1;
}
leaf[v]=0;
for(int i=0;i<son[v].size();i++) {
leaf[v]+=getleaf(son[v][i]);
}
return leaf[v];
}
int ans(int v) {
if (dp[v]!=nn) {
return dp[v];
}
if (p[v]==-1) {
return 0;
}
int got=ans(p[v]);
if (leaf[v]%2==0)
got--;
else
got++;
return dp[v]=got;
}
void dfs(int v,int prev) {
p[v]=prev;
sz[v]=1;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (prev==nt) {
continue;
}
son[v].push_back(nt);
dfs(nt,v);
sz[v]+=sz[nt];
if (sz[son[v][0]]<sz[nt]) {
swap(son[v][0],son[v][son[v].size()-1]);
}
}
}
void dfs_hld(int v) {
ind[v]=f++;
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
top[nt]=(i==0?top[v]:nt);
dfs_hld(nt);
}
}
bool comp(int a,int b) {
return ind[a]<ind[b];
}
int main(void) {
int n,q;
scanf("%d %d",&n,&q);
memset(leaf,-1,sizeof(leaf));
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
u--;
v--;
deg[u]++;
deg[v]++;
adj[u].push_back(v);
adj[v].push_back(u);
}
int r=0;
for(int i=0;i<n;i++) {
dp[i]=nn;
p[i]=-1;
if (deg[i]!=1) {
r=i;
}
}
dfs(r,-1);
top[r]=r;
dfs_hld(r);
int ori=0;
for(int i=0;i<n;i++) {
rev[ind[i]]=i;
}
for(int i=n-1;i>=0;i--) {
if (son[rev[i]].empty()) {
leaf[rev[i]]=1;
continue;
}
leaf[rev[i]]=0;
for(int j=0;j<son[rev[i]].size();j++) {
leaf[rev[i]]+=leaf[son[rev[i]][j]];
}
if (i&&leaf[rev[i]]%2==0) {
ori++;
}
}
for(int i=0;i<n;i++) {
if (i!=r) {
seg[i+s]=(leaf[i]%2==0?1:0);
}
}
for(int i=s-1;i>0;i--) {
seg[i]=seg[i*2]+seg[i*2+1];
}
for(int i=0;i<q;i++) {
int k;
vector<int> save0;
scanf("%d",&k);
int ret=n-1+k;
vector<int> save;
int l=leaf[r];
for(int j=0;j<k;j++) {
int v;
scanf("%d",&v);
v--;
save0.push_back(v);
if (!son[v].empty()||cnt[v]>0) {
save.push_back(v);
l++;
}
cnt[v]++;
}
if (l%2!=0) {
printf("-1\n");
for(int j=0;j<save0.size();j++) {
cnt[save0[j]]--;
}
continue;
}
sort(save.begin(),save.end(),comp);
reverse(save.begin(),save.end());
for(int j=0;j<save.size();j++) {
int now=save[j];
while (now!=-1) {
update(ind[top[now]],ind[now]);
now=p[top[now]];
}
}
printf("%d\n",ret+sum(1,n-1));
for(int j=0;j<save.size();j++) {
int now=save[j];
while (now!=-1) {
update(ind[top[now]],ind[now]);
now=p[top[now]];
}
}
for(int j=0;j<save0.size();j++) {
cnt[save0[j]]--;
}
}
}
Compilation message
cleaning.cpp: In function 'int getleaf(int)':
cleaning.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs_hld(int)':
cleaning.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int j=0;j<son[rev[i]].size();j++) {
| ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:191:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for(int j=0;j<save0.size();j++) {
| ~^~~~~~~~~~~~~
cleaning.cpp:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int j=0;j<save.size();j++) {
| ~^~~~~~~~~~~~
cleaning.cpp:206:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int j=0;j<save.size();j++) {
| ~^~~~~~~~~~~~
cleaning.cpp:213:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | for(int j=0;j<save0.size();j++) {
| ~^~~~~~~~~~~~~
cleaning.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
174 | scanf("%d",&k);
| ~~~~~^~~~~~~~~
cleaning.cpp:180:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
180 | scanf("%d",&v);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5996 KB |
Output is correct |
| 2 |
Incorrect |
180 ms |
8044 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
7396 KB |
Output is correct |
| 2 |
Correct |
17 ms |
7272 KB |
Output is correct |
| 3 |
Correct |
49 ms |
13928 KB |
Output is correct |
| 4 |
Correct |
93 ms |
12388 KB |
Output is correct |
| 5 |
Correct |
100 ms |
14820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
8052 KB |
Output is correct |
| 2 |
Correct |
23 ms |
8040 KB |
Output is correct |
| 3 |
Correct |
76 ms |
25836 KB |
Output is correct |
| 4 |
Correct |
139 ms |
24928 KB |
Output is correct |
| 5 |
Correct |
66 ms |
23788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
8556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
11756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
318 ms |
15724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5996 KB |
Output is correct |
| 2 |
Incorrect |
180 ms |
8044 KB |
Output isn't correct |
