// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,popcnt")
#include <bits/stdc++.h>
#define lli long long int
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define MP make_pair
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 2e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;
const int LGN = 20;
int n, q;
vector<vector<int> > adj(N, vector<int>());
array<vector<int>, LGN> anc;
array<vector<int>, LGN> diff;
vector<int> dep(N, 0);
vector<int> tin(N, 0);
//virt stuff
vector<bool> mark(N, 0);
vector<int> vals(N, 0);
vector<vector<int> > virt(N, vector<int>());
vector<int> p(N, 0);
int tim = 0;
int ans = 0;
int leaf = 0;
int dfs(int node, int par) {
anc[0][node] = par;
tin[node] = tim++;
if(adj[node].size() == 1 && par) {
leaf++;
ans++;
diff[0][node] = 1;
return 1;
}
int ret = 0;
if(par == 0 && adj[node].size() == 1) leaf++;
for(auto c : adj[node]) {
if(c == par) continue;
dep[c] = dep[node] + 1;
ret += dfs(c, node);
}
// cout << "node: " << node << " ret:" << ret << "\n";
if(par == 0) {
return 0;
}
if(ret & 1) {
ans++;
diff[0][node] = 1;
return 1;
}
else {
ans += 2;
diff[0][node] = -1;
return 2;
}
}
void calc() {
for(int k = 1; k < LGN; k++) {
for(int i = 1; i <= n; i++) {
anc[k][i] = anc[k - 1][anc[k - 1][i]];
diff[k][i] = diff[k - 1][i] + (diff[k - 1][anc[k - 1][i]]);
}
}
}
int kth_anc(int x, int k) {
for(int i = 0; i < LGN; i++) {
if(k & (1 << i)) x = anc[i][x];
}
return x;
}
int k_sum(int x, int k) {
int ret = 0;
for(int i = 0; i < LGN; i++) {
if(k & (1 << i)) {
ret += diff[i][x];
x = anc[i][x];
}
}
return ret;
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
y = kth_anc(y, dep[y] - dep[x]);
if(x == y) return x;
for(int i = LGN - 1; i >= 0; i--) {
if(anc[i][x] != anc[i][y]) {
x = anc[i][x];
y = anc[i][y];
}
}
return anc[0][x];
}
int res = 0;
bool dfs2(int node, int par) {
bool cur = mark[node];
for(auto c : virt[node]) {
assert(c != par);
cur ^= dfs2(c, node);
}
if(cur) {
res += vals[node];
}
return cur;
}
void solve() {
cin >> n >> q;
REP(i, n - 1) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
REP(i, LGN) {
anc[i].assign(n + 3, 0);
diff[i].assign(n + 3, 0);
}
dfs(1, 0);
anc[0][1] = 1;
calc();
auto comp = [](int x, int y) {
return tin[x] < tin[y];
};
// cout << "ans:" << ans << "\n";
// for(int i = 1; i <= n; i++) {
// cout << "i:" << i << " dif:" << diff[0][i] << "\n";
// }
REP(z, q) {
// cout << "query:" << z << endl;
int d;
cin >> d;
res = ans + d;
int lv = leaf + d;
vector<int> a(d);
REP(i, d) {
cin >> a[i];
}
sort(all(a));
vector<array<int, 2> > tmp;
for(int i = 0; i < d; i++) {
if(tmp.size() && tmp.back()[0] == a[i]) tmp[tmp.size() - 1][1]++;
else {
tmp.pb({a[i], 1});
}
}
a.clear();
for(auto &c : tmp) {
if(adj[c[0]].size() == 1) {
lv--;
}
}
if(lv & 1) {
cout << "-1\n";
continue;
}
// cout << "new a: ";
for(auto &c : tmp) {
if((c[1] & 1) && (adj[c[0]].size() > 1)) {
a.pb(c[0]);
// cout << c[0] << " ";
}
else if(!(c[1] & 1)) {
a.pb(c[0]);
}
}
// cout << endl;
if(a.empty()) {
cout << res << "\n";
continue;
}
for(auto c : a) {
mark[c] = 1;
}
sort(all(a), comp);
// cout << "aaa" << endl;
d = (int)a.size();
for(int i = 0; i < d - 1; i++) {
a.pb(lca(a[i], a[i + 1]));
}
sort(all(a), comp);
a.resize(unique(all(a)) - a.begin());
d = (int) a.size();
vector<int> st;
st.pb(a[0]);
for(int i = 1; i < d; i++) {
assert(st.size());
while(lca(st.back(), a[i]) != st.back()) {
st.pop_back();
assert(st.size());
}
virt[st.back()].pb(a[i]);
p[a[i]] = st.back();
st.pb(a[i]);
}
vals[a[0]] = k_sum(a[0], dep[a[0]] - dep[1] + 1);
for(int i = 1; i < d; i++) {
vals[a[i]] = k_sum(a[i], dep[a[i]] - dep[p[a[i]]]);
}
// for(int i = 0; i < d; i++) {
// cout << "ai:" << a[i] << " val:" << vals[a[i]] << " mark:" << mark[a[i]] << "\n";
// }
// cout << "res before:" << res << "\n";
dfs2(a[0], 0);
cout << res << "\n";
for(auto c : a) {
mark[c] = 0;
vals[c] = 0;
p[c] = 0;
virt[c].clear();
}
}
}
signed main() {
fastio();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
12888 KB |
Output is correct |
| 2 |
Incorrect |
44 ms |
17128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
13912 KB |
Output is correct |
| 2 |
Correct |
14 ms |
13932 KB |
Output is correct |
| 3 |
Correct |
37 ms |
32272 KB |
Output is correct |
| 4 |
Correct |
46 ms |
27596 KB |
Output is correct |
| 5 |
Correct |
57 ms |
33644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
17492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
25680 KB |
Output is correct |
| 2 |
Incorrect |
98 ms |
26960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
32472 KB |
Output is correct |
| 2 |
Correct |
72 ms |
36432 KB |
Output is correct |
| 3 |
Correct |
87 ms |
35800 KB |
Output is correct |
| 4 |
Correct |
77 ms |
36672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
12888 KB |
Output is correct |
| 2 |
Incorrect |
44 ms |
17128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
