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>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
const int LOG=25;
int n, q;
vector<vector<int>> adj;
vector<vector<int>> m;
vector<int> depth;
vector<int> a;
vector<int> empls;
vector<int> numerotation;
vector<vector<int>> graph;
map<int, int> mp;
vector<int> prefix;
vector<int> parity;
vector<int> parent;
vector<pair<int, int>> isin;
int cntleaf=0, tot=0;
int ans=0;
void dfsdepth(int s, int lst, int &act) {
isin[s].first=act++;
if (adj[s].size()==1) prefix[s]++;
for (auto u: adj[s]) {
if (u==lst) continue;
parent[u]=s;
depth[u]=depth[s]+1;
dfsdepth(u, s, act);
prefix[s]+=prefix[u];
a.push_back(s);
a.push_back(u);
}
isin[s].second=act++;
return;
}
void dfsparity(int s, int lst=-1) {
for (auto u: adj[s]) {
if (u==lst) continue;
parity[u]=parity[s]+(prefix[u]+1)%2;
dfsparity(u, s);
}
if (lst==-1) tot+=n-1;
else tot+=(prefix[s]+1)%2;
return;
}
int dfstot(int s, int lst) {
int comp=mp[s];
for (auto u: graph[s]) {
comp+=dfstot(u, s);
}
if (sz(adj[s])<2) comp++;
if (comp%2==1) {
int temp=parity[s], d=depth[s];
if (lst>=0) temp-=parity[lst], d-=depth[lst];
ans-=temp;
ans+=d-temp;
}
if (sz(adj[s])<2) comp--;
return comp;
}
void sparsetable() {
m.clear();
m.resize(sz(a)+5, vector<int>(LOG, 0));
for (int i=0; i<sz(a); i++) {
if (empls[a[i]]==-1) empls[a[i]]=i;
m[i][0]=a[i];
}
for (int k=1; k<LOG; k++) {
for (int i=0; i+(1<<k)-1 < n; i++) {
m[i][k]=min(m[i][k-1], m[i+(1<<(k-1))][k-1]);
}
}
}
int lca(int u, int v) {
int l=empls[u], r=empls[v];
if (l>r) swap(l, r);
int len=r-l+1, k=log2(len);
return min(m[l][k], m[r-(1<<k)+1][k]);
}
int ALLPROBLEM() {
int lst=cntleaf;
while(q--) {
cntleaf=lst;
int d; cin >> d;
mp.clear();
vector<pair<int, int>> change(d);
for (auto &u: change) {
cin >> u.second, u.second--;
u.second=numerotation[u.second];
u.first=isin[u.second].first;
if (sz(adj[u.second])>1 || mp[u.second]) cntleaf++;
mp[u.second]++;
}
if (cntleaf%2==1) {
cout << -1 << endl;
continue;
}
sort(change.begin(), change.end());
set<int> L;
for (auto u: change) {
if (L.empty()) {
L.insert(u.second);
continue;
}
auto next=L.upper_bound(u.second);
if (next==L.end()) next--;
auto prec=L.lower_bound(u.second);
if (prec!=L.begin()) prec--;
L.insert(u.second);
L.insert(lca(u.second, *prec));
L.insert(lca(u.second, *next));
}
vector<pair<int, int>> vec;
for (auto u=L.begin(); u!=L.end(); u++) {
vec.push_back({isin[*u].first, *u});
}
sort(vec.begin(), vec.end());
stack<int> act;
act.push(vec[0].second);
for (int i=1; i<sz(vec); i++) {
int u=vec[i].second;
while (isin[act.top()].second<isin[u].first) act.pop();
graph[act.top()].push_back(u);
act.push(vec[i].second);
}
ans=tot+d;
dfstot(vec[0].second, 0);
cout << ans << endl;
for (auto u: vec) graph[u.second].clear();
}
return 0;
}
int solve() {
cin >> n >> q;
adj.resize(n);
graph.resize(n);
numerotation.resize(n);
empls.resize(n, -1);
depth.resize(n, 0);
prefix.resize(n, 0);
parity.resize(n, 0);
isin.resize(n);
parent.resize(n);
for (int i=0; i<n-1; i++) {
int u, v; cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto u: adj) if (sz(u)==1) cntleaf++;
int begining=0;
while (sz(adj[begining])<2) begining++;
queue<pair<int, int>> myqueue;
myqueue.push({begining, -1});
int act=0;
while (!myqueue.empty()) {
int s=myqueue.front().first, lst=myqueue.front().second; myqueue.pop();
numerotation[s]=act++;
for (auto &u: adj[s]) {
if (u!=lst) myqueue.push({u, s});
}
}
vector<vector<int>> newadj=adj;
adj.clear();
adj.resize(n);
for (int i=0; i<n; i++) {
adj[numerotation[i]]=newadj[i];
for (auto &u: adj[numerotation[i]]) {
u=numerotation[u];
}
}
int temp=0;
dfsdepth(0, -1, temp);
dfsparity(0);
sparsetable();
return ALLPROBLEM();
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | 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... |