#include <bits/stdc++.h>
#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << endl;\
}
#define outputvec(a){\
for(auto x:a){\
cout << (int)x << " ";\
}\
cout << endl;\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],c[MAX],sub[MAX],e[MAX],tp[MAX],dep[MAX],tim,pre[MAX],e1[MAX];
ll res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//int e[1001][1001];
//bool e1[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> g;
void dfs(int v,int prev){
pre[v]=prev;
e[v]=tim++;
sub[v]=1;
c[v]=(g[v].size()==1);
for(auto x:g[v]){
if(x==prev){
continue;
}
dep[x]=dep[v]+1;
dfs(x,v);
c[v]+=c[x];
sub[v]+=sub[x];
}
}
void dfs_hld(int v,int prev,int top){
int mx,ind_mx;
mx=-INF;
ind_mx=-1;
tp[v]=top;
for(auto x:g[v]){
if(x==prev){
continue;
}
if(sub[x]>mx){
mx=sub[x];
ind_mx=x;
}
}
if(ind_mx==-1){
return;
}
dfs_hld(ind_mx,v,top);
for(auto x:g[v]){
if(x==prev || x==ind_mx){
continue;
}
dfs_hld(x,v,x);
}
}
struct segtree{
vector<int> sums;
vector<int> lazy;
int sz=0;
void init(int n){
sz=1;
while(sz<n){
sz*=2;
}
sums.resize(2*sz,0);
lazy.resize(2*sz,0);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
sums[x]=a[lx];
}
return;
}
int mid=(lx+rx)/2;
build(2*x+1,lx,mid,a);
build(2*x+2,mid,rx,a);
sums[x]=sums[2*x+1]+sums[2*x+2];
}
void build(vector<int> &a){
build(0,0,sz,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1 || !lazy[x]){
return;
}
int mid=(lx+rx)/2;
sums[2*x+1]=mid-lx-sums[2*x+1];
sums[2*x+2]=rx-mid-sums[2*x+2];
lazy[2*x+1]^=1;
lazy[2*x+2]^=1;
lazy[x]=0;
}
void upd(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return;
}
if(lx>=l && rx<=r){
sums[x]=rx-lx-sums[x];
lazy[x]^=1;
return;
}
int mid=(lx+rx)/2;
upd(2*x+1,lx,mid,l,r);
upd(2*x+2,mid,rx,l,r);
sums[x]=sums[2*x+1]+sums[2*x+2];
}
void upd(int l,int r){
if(l==n || l==r){
return;
}
upd(0,0,sz,l,r);
}
int get_sum(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return 0;
}
if(lx>=l && rx<=r){
return sums[x];
}
int mid=(lx+rx)/2;
int s1=get_sum(2*x+1,lx,mid,l,r);
int s2=get_sum(2*x+2,mid,rx,l,r);
return s1+s2;
}
int get_sum(int l,int r){
return get_sum(0,0,sz,l,r);
}
};
segtree st;
void upd(int x){
while(tp[x]!=1){
st.upd(e[tp[x]],e[x]+1);
//cout << e[tp[x]] << " " << e[x] << "\n";
x=pre[tp[x]];
}
st.upd(e[1],e[x]+1);
//cout << e[1] << " " << e[x] << "z\n";
}
void solve(){
cin >> n >> q;
g.clear();
g.resize(n+1);
for(int i=0;i<n-1;i++){
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs(1,1);
dfs_hld(1,1,1);
vector<int> d(n);
for(int i=1;i<=n;i++){
d[e[i]]=1-c[i]%2;
//cout << i << " " << e[i] << "\n";
}
//outputvec(d);
set<int> f;
st.init(n);
st.build(d);
for(int i=0;i<q;i++){
cin >> m;
f.clear();
for(int j=0;j<m;j++){
cin >> e1[j];
x=e1[j];
if((int)g[x].size()!=1 || f.find(x)!=f.end()){
upd(x);
}
f.ins(x);
}
if(st.get_sum(0,1)==0){
cout << -1 << "\n";
}
else{
cout << st.get_sum(0,n)+n+m-2 << "\n";
}
f.clear();
for(int j=0;j<m;j++){
x=e1[j];
if((int)g[x].size()!=1 || f.find(x)!=f.end()){
upd(x);
}
f.ins(x);
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input1.txt","r",stdin);
//cin >> t;
ll cnt1=1;
while(t--){
solve();
}
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:235:8: warning: unused variable 'cnt1' [-Wunused-variable]
235 | ll cnt1=1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
43708 KB |
Output is correct |
| 2 |
Incorrect |
137 ms |
49024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
46428 KB |
Output is correct |
| 2 |
Correct |
70 ms |
46656 KB |
Output is correct |
| 3 |
Correct |
41 ms |
62404 KB |
Output is correct |
| 4 |
Correct |
121 ms |
60476 KB |
Output is correct |
| 5 |
Correct |
141 ms |
65696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
47432 KB |
Output is correct |
| 2 |
Correct |
65 ms |
47448 KB |
Output is correct |
| 3 |
Correct |
58 ms |
69532 KB |
Output is correct |
| 4 |
Correct |
170 ms |
69312 KB |
Output is correct |
| 5 |
Correct |
42 ms |
65872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
49700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
56624 KB |
Output is correct |
| 2 |
Correct |
209 ms |
56588 KB |
Output is correct |
| 3 |
Correct |
168 ms |
50400 KB |
Output is correct |
| 4 |
Correct |
222 ms |
56664 KB |
Output is correct |
| 5 |
Correct |
207 ms |
56700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
63432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
43708 KB |
Output is correct |
| 2 |
Incorrect |
137 ms |
49024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
