#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
struct SEG {
int n;
vector<int> a;
vector<int> lz;
SEG(int _n):n(_n) {
a.resize(4*n+10);
lz.resize(4*n+10);
}
void init(int l,int r,int id,vector<int> &ans) {
if (l==r) {
a[id]=ans[l];
return;
}
int mid=l+r>>1;
init(l,mid,id<<1,ans);
init(mid+1,r,id<<1|1,ans);
a[id]=a[id<<1]+a[id<<1|1];
}
void pd(int l,int r,int id) {
if (l==r) return;
if (lz[id]) {
int mid=l+r>>1;
a[id<<1]=3*(mid-l+1)-a[id<<1];
a[id<<1|1]=3*(r-mid)-a[id<<1|1];
lz[id<<1]^=1;
lz[id<<1|1]^=1;
lz[id]=0;
}
}
void update(int L,int R,int l,int r,int id) {
// cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<id<<" u L R l r id\n"<<flush;
if (L<=l and r<=R) {
a[id]=3*(r-l+1)-a[id];
lz[id]^=1;
return;
}
int mid=l+r>>1;
pd(l,r,id);
if (L<=mid) update(L,R,l,mid,id<<1);
if (mid<R) update(L,R,mid+1,r,id<<1|1);
a[id]=a[id<<1]+a[id<<1|1];
}
int query(int L,int R,int l,int r,int id) {
// cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<id<<" q L R l r id\n"<<flush;
if (L<=l and r<=R) return a[id];
int mid=l+r>>1;
pd(l,r,id);
int ans=0;
if (L<=mid) ans+=query(L,R,l,mid,id<<1);
if (mid<R) ans+=query(L,R,mid+1,r,id<<1|1);
return ans;
}
};
void dfs1(int v,int p,vvector<int> &G,vector<int> &hc,vector<int> &sz,vvector<int> &fa,vector<int> &dep) {
sz[v]=1;
hc[v]=-1;
dep[v]=dep[p]+1;
fa[v][0]=p;
for (int i=1;i<20;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
for (int i:G[v]) {
if (i==p) continue;
dfs1(i,v,G,hc,sz,fa,dep);
sz[v]+=sz[i];
if (hc[v]==-1 or sz[i]>sz[hc[v]]) hc[v]=i;
}
}
void dfs2(int v,int p,vvector<int> &G,vector<int> &head,int hd,vector<int> &hc,vector<int> &dfn,int &tm) {
head[v]=hd;
dfn[v]=tm++;
if (hc[v]!=-1) dfs2(hc[v],v,G,head,hd,hc,dfn,tm);
for (int i:G[v]) {
if (i==p or i==hc[v]) continue;
dfs2(i,v,G,head,i,hc,dfn,tm);
}
}
void dfs3(int v,int p,vvector<int> &G,vector<int> &lvc,vector<int> &dfn) {
lvc[dfn[v]]=(G[v].size()==1);
for (int i:G[v]) {
if (i==p) continue;
dfs3(i,v,G,lvc,dfn);
lvc[dfn[v]]+=lvc[dfn[i]];
}
if (lvc[dfn[v]]&1) lvc[dfn[v]]=1;
else lvc[dfn[v]]=2;
}
int get(int v,vector<int> &head,vector<int> &dfn,SEG &seg,vvector<int> &fa,int n) {
int ans=0;
while (v) {
ans+=seg.query(dfn[head[v]],dfn[v],1,n,1);
v=fa[head[v]][0];
}
return ans;
}
void rev(int v,vector<int> &head,vector<int> &dfn,SEG &seg,vvector<int> &fa,int n) {
while (v) {
seg.update(dfn[head[v]],dfn[v],1,n,1);
v=fa[head[v]][0];
}
}
int main() {
speed;
freopen("C:\\Users\\UM3504DA\\Downloads\\sample\\input1.txt","r",stdin);
freopen("C:\\Users\\UM3504DA\\Downloads\\sample\\op1.txt","w+",stdout);
int n,q;
cin>>n>>q;
vvector<int> G(n+1);
int rt=0;
for (int i=0;i<n-1;i++) {
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
int ttlv=0;
for (int i=1;i<=n;i++) {
if (G[i].size()>1) rt=i;
else ttlv++;
}
vector<int> head(n+1),hc(n+1),dfn(n+1),sz(n+1),dep(n+1);
vvector<int> fa(n+1,vector<int>(20));
int tm=1;
dfs1(rt,0,G,hc,sz,fa,dep);
// cout<<"D1\n"<<flush;
dfs2(rt,0,G,head,rt,hc,dfn,tm);
// cout<<"D2\n"<<flush;
SEG seg(n);
vector<int> lvc(n+1);
dfs3(rt,0,G,lvc,dfn);
// cout<<"D3\n"<<flush;
seg.init(1,n,1,lvc);
// cout<<"segD\n"<<flush;
ll ans=seg.query(1,n,1,n,1);
// cout<<"segQ\n"<<flush;
while (q--) {
int d;
cin>>d;
vector<int> nds(d);
map<int,int> exd;
for (int &i:nds) cin>>i;
int dta=0;
int dtl=0;
for (int i:nds) {
if (G[i].size()+exd[i]!=1) {
dta+=3*dep[i]-2*get(i,head,dfn,seg,fa,n);
rev(i,head,dfn,seg,fa,n);
}
exd[i]++;
}
for (auto [i,x]:exd) {
dtl+=x;
dtl-=(G[i].size()==1);
}
if ((ttlv+dtl)&1) cout<<"-1\n";
else cout<<ans+dta-seg.query(dfn[rt],dfn[rt],1,n,1)+d<<"\n";
for (int i:nds) {
exd[i]--;
if (G[i].size()+exd[i]!=1) {
rev(i,head,dfn,seg,fa,n);
}
}
}
return 0;
}
/*
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
*/
Compilation message
cleaning.cpp: In member function 'void SEG::init(int, int, int, std::vector<int>&)':
cleaning.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid=l+r>>1;
| ~^~
cleaning.cpp: In member function 'void SEG::pd(int, int, int)':
cleaning.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=l+r>>1;
| ~^~
cleaning.cpp: In member function 'void SEG::update(int, int, int, int, int)':
cleaning.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid=l+r>>1;
| ~^~
cleaning.cpp: In member function 'int SEG::query(int, int, int, int, int)':
cleaning.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid=l+r>>1;
| ~^~
cleaning.cpp: In function 'int main()':
cleaning.cpp:133:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen("C:\\Users\\UM3504DA\\Downloads\\sample\\input1.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen("C:\\Users\\UM3504DA\\Downloads\\sample\\op1.txt","w+",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
690 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
625 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
613 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
613 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
629 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
646 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
690 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
