This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e5+10,mod = 1e9+7,inf = 1e9,sq = 500,maxm = 1e5+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int n,ll k){
int c = 1;
while (k){
if (k&1) c = (1ll*c*n)%mod;
n = (1ll*n*n)%mod;
k >>= 1;
}
return c;
}
vector<int> adj[N];
bool leaf[N],vis[N];
int ans,par[N][20],h[N],tin[N],T;
int cnt[N][2],L[N],R[N];
void dfs(int v,int p){
par[v][0] = p;
tin[v] = T;
T++;
for (int u : adj[v]){
if (u == p) continue;
h[u] = h[v]+1;
dfs(u,v);
if (leaf[u]){
ans++;
leaf[v] = !leaf[v];
}
else ans += 2;
}
if(adj[v].size() == 1) leaf[v] = 1;
}
inline int lca(int u,int v){
if (h[u] > h[v]) swap(u,v);
repr(i,19,0){
if (h[v]-h[u] >= (1 << i))
v = par[v][i];
}
if (u == v) return v;
repr(i,19,0){
if (par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
void dfs2(int v){
for (int u : adj[v]){
if(u == par[v][0]) continue;
cnt[u][0] = cnt[v][0];
cnt[u][1] = cnt[v][1];
cnt[u][leaf[u]]++;
dfs2(u);
}
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,q;
cin >> n >> q;
int r = -1;
rep(i,1,n){
int u,v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
if (adj[u].size() == 2) r = u;
else if (adj[v].size() == 2) r = v;
}
dfs(r,-1);
dfs2(r);
rep(j,1,19){
rep(i,1,n+1){
if (h[i] < (1 << j)) continue;
par[i][j] = par[par[i][j-1]][j-1];
}
}
while (q--){
int t,out;
cin >> t;
out = ans+t;
vector<int> ve;
vector<pll> ve2;
ve.reserve(t);
rep(i,0,t){
int p;
cin >> p;
ve.pb(p);
if (adj[p].size() > 1 || vis[p])
ve2.pb({tin[p],p});
else vis[p] = 1;
}
rep(i,0,t) vis[ve[i]] = 0;
sort(ve2.begin(),ve2.end());
set<pll> st;
set<int> st2;
int sz = ve2.size();
if (leaf[r] != (sz&1)){
cout << -1 << endl;
continue;
}
if (!sz){
cout << out << endl;
continue;
}
rep(i,0,sz-1){
int w = lca(ve2[i].Y,ve2[i+1].Y);
st.insert({-h[w],i});
st2.insert(i);
L[i] = i-1;
R[i] = i+1;
}
R[sz-1] = sz;
st2.insert(sz-1);
while (!st.empty()){
pll p = *(st.begin());
st.erase(st.begin());
int v = ve2[p.Y].Y;
int u = ve2[R[p.Y]].Y;
st2.erase(R[p.Y]);
st2.erase(p.Y);
int w = lca(u,v);
out = out+(cnt[v][1]+cnt[u][1]-2*cnt[w][1])-(cnt[v][0]+cnt[u][0]-2*cnt[w][0]);
if (L[p.Y] != -1){
R[L[p.Y]] = R[R[p.Y]];
st.erase({-h[lca(v,ve2[L[p.Y]].Y)],L[p.Y]});
}
if (R[R[p.Y]] < sz){
L[R[R[p.Y]]] = L[p.Y];
st.erase({-h[lca(u,ve2[R[R[p.Y]]].Y)],R[p.Y]});
}
if (L[p.Y] != -1 && R[R[p.Y]] < sz)
st.insert({-h[lca(ve2[L[p.Y]].Y,ve2[R[R[p.Y]]].Y)],L[p.Y]});
}
if (!st2.empty()){
int ind = *(st2.begin());
int u = ve2[ind].Y;
out = out + cnt[u][1]-cnt[u][0];
}
rep(i,0,sz-1) L[i] = R[i] = 0;
cout << out << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |