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;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll L = 20;
const ll N = 1e5 + 50;
const ll Mod = 1e9 + 7;
ll n, q, r, sz[N], cnt[N], h[N], sum[N], par[N][L], st[N], timer, upd[N], head[N];
vector<int> adj[N];
void dfs(int v, int p = 0){
par[v][0] = p;
for(int i = 1; i < L; i++){
if(!par[v][i-1]) break;
par[v][i] = par[par[v][i-1]][i-1];
}
sz[v] = 1;
st[v] = ++timer;
for(int u: adj[v]){
if(u == p) continue;
h[u] = h[v] + 1; dfs(u, v);
sz[v] += sz[u]; cnt[v] += cnt[u];
}
if(sz[v] == 1) cnt[v]++;
}
int getPar(int v, int k){
for(int i = 0; i < L; i++){
if(k >> i & 1) v = par[v][i];
}
return v;
}
int lca(int u, int v){
if(h[v] < h[u]) swap(u, v);
v = getPar(v, h[v] - h[u]);
if(u == v) return v;
for(int i = L-1; i >= 0; i--){
if(par[v][i] != par[u][i]){
v = par[v][i]; u = par[u][i];
}
}
return par[v][0];
}
void pre(int v, int p = 0){
sum[v] = sum[p] + (cnt[v] % 2);
for(int u: adj[v]){
if(u != p) pre(u, v);
}
}
bool cmp(int i, int j){
return st[i] < st[j];
}
int main(){
fast_io;
cin >> n >> q;
int u, v;
for(int i = 1; i < n; i++){
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
r = 1;
while(adj[r].size() == 1) r++;
dfs(r); pre(r);
ll ans = 2 * (n-1);
for(int i = 1; i <= n; i++) if(i != r) ans -= (cnt[i] % 2);
//cout << ans << endl;
while(q--){
int d, x; cin >> d;
vector<int> vec, vert;
for(int i = 1; i <= d; i++){
cin >> x; vec.pb(x); upd[x]++;
}
sort(all(vec), cmp);
vec.resize(unique(all(vec)) - vec.begin());
for(int i: vec) if(adj[i].size() == 1) upd[i]--;
set<pii> ms;
for(int i: vec) ms.insert(Mp(st[i], i));
while(ms.size() > 1){
auto lst = ms.end();
auto lst1 = lst; lst1--;
auto lst2 = lst1; lst2--;
int ulv = lca(lst1 -> S, lst2 -> S);
head[lst1 -> S] = ulv;
vert.pb(lst1 -> S);
ms.erase(lst1);
ms.insert(Mp(st[ulv], ulv));
}
vert.pb(ms.begin() -> S);
if(vert.back() != r) head[vert.back()] = r;
for(int i: vert){
if(head[i]) upd[head[i]] += upd[i];
}
ll res = ans;
for(int i: vert){
//cout << i << sep << head[i] << sep << upd[i] << endl;
if(!head[i]) continue;
if(upd[i] % 2){
res += sum[i] - sum[head[i]];
res -= h[i] - h[head[i]] - (sum[i] - sum[head[i]]);
}
}
if((cnt[r] + upd[r]) % 2) cout << -1 << endl;
else cout << res + d << endl;
for(int i: vert){
head[i] = 0; upd[i] = 0;
}
upd[r] = 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... |