#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q;
vector < int > adj[maxn];
void input()
{
cin >> n >> q;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
}
int find_leaves(int v, int par)
{
int cnt = 0, children = 0;
for (int u : adj[v])
{
if (u == par)
continue;
cnt += find_leaves(u, v);
children ++;
}
if (par == -1 && children == 1)
cnt ++;
if (children == 0)
cnt ++;
return cnt;
}
int parent[maxn], is_leaf[maxn];
int tin[maxn], tout[maxn], timer, occ[2 * maxn];
ll depth[maxn];
void calc(int v, int par)
{
occ[++ timer] = v;
tin[v] = timer;
parent[v] = par;
is_leaf[v] = true;
for (int u : adj[v])
{
if (u == par)
continue;
is_leaf[v] = false;
depth[u] = depth[v] + 1;
calc(u, v);
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 21;
int dp[maxlog][maxn * 2], lg[2 * maxn];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < maxlog; j ++)
for (int i = 1; i <= (n - (1 << j)) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1, lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
ll get_distance(int v, int u)
{
return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}
ll added[maxn];
ll sum[maxn], cnt[maxn];
int all = 0;
void find_depths(int v)
{
all ++;
sum[v] = cnt[v] = 0;
bool leaf = true;
for (int u : adj[v])
{
if (u == parent[v])
continue;
find_depths(u);
cnt[v] += cnt[u];
sum[v] += sum[u];
leaf = false;
}
sum[v] = sum[v] + added[v] * (depth[v] + 1);
cnt[v] += added[v];
if (leaf && added[v] == 0)
sum[v] = sum[v] + depth[v], cnt[v] ++;
ll pairs = cnt[v] / 2;
if (pairs * 2 == cnt[v])
pairs --;
sum[v] = sum[v] - pairs * depth[v] * (ll)2;
cnt[v] -= pairs * 2;
added[v] = 0;
//cout << "state " << v << " " << cnt_leaves << " " << ans << endl;
}
ll sub[maxn];
void dfs(int v)
{
sub[v] = 0;
int child = 0;
for (int u : adj[v])
{
if (u == parent[v])
continue;
dfs(u);
sub[v] = sub[v] + sub[u];
child ++;
}
if (child == 0)
sub[v] = 1;
}
bool cmp(int v, int u)
{
return tin[v] < tin[u];
}
ll c1[maxn], c2[maxn];
vector < int > vir[maxn];
ll cnt_on[maxn];
pair < ll, ll > vir_dfs(int v, int par)
{
ll cnt = 0, sum = 0;
for (int u : vir[v])
{
pair < ll, ll > res = vir_dfs(u, v);
cnt += res.second;
sum += res.first;
}
cnt = cnt + cnt_on[v];
cnt %= 2;
if (cnt == 1)
{
///cout << c1[v] << " : " << c1[par] << endl;
////cout << c2[v] << " : " << c2[par] << endl;
ll d1 = c1[v] - c1[par];
ll d2 = c2[v] - c2[par];
sum = sum + d1 - d2;
}
///cout << v << " : " << sum << " : " << cnt << endl;
return {sum, cnt};
}
ll virtual_tree(vector < int > nodes)
{
if (nodes.empty())
return 0;
for (int cur : nodes)
cnt_on[cur] ++;
sort(nodes.begin(), nodes.end(), cmp);
vector < int > nc;
for (int i = 1; i < nodes.size(); i ++)
{
///cout << get_lca(nodes[i - 1], nodes[i]) << " " << nodes[i - 1] << " " << nodes[i] << endl;
nc.push_back(get_lca(nodes[i - 1], nodes[i]));
}
for (int cur : nc)
nodes.push_back(cur);
nc.clear();
sort(nodes.begin(), nodes.end());
for (int cur : nodes)
{
if (nc.empty() || cur != nc.back())
nc.push_back(cur);
}
nodes = nc;
sort(nodes.begin(), nodes.end(), cmp);
for (int cur : nodes)
vir[cur].clear();
vector < int > st;
for (int i = 0; i < nodes.size(); i ++)
{
///cout << nodes[i] << " ";
while (!st.empty() && get_lca(nodes[i], st.back()) != st.back())
st.pop_back();
if (!st.empty())
{
///cout << "edge " << st.back() << " " << nodes[i] << endl;
vir[st.back()].push_back(nodes[i]);
}
st.push_back(nodes[i]);
}
ll ans = vir_dfs(st[0], -1).first;
for (int cur : nodes)
cnt_on[cur] = 0;
return ans;
}
void push_down(int v)
{
if (sub[v] % 2 == 1)
c1[v] ++;
else
c2[v] ++;
for (int u : adj[v])
{
if (u == parent[v])
continue;
c1[u] = c1[v];
c2[u] = c2[v];
push_down(u);
}
}
void answer_queries()
{
int root = 1;
while(adj[root].size() == 1)
root ++;
calc(root, -1);
build_sparse_table();
dfs(root);
push_down(root);
int sum = 0;
for (int i = 1; i <= n; i ++)
{
if (i == root)
continue;
if (sub[i] % 2 == 0)
sum += 2;
else
sum ++;
}
///cout << sum << endl;
for (int i = 1; i <= q; i ++)
{
int d;
cin >> d;
set < int > nodes;
for (int j = 0; j < d; j ++)
{
int x;
cin >> x;
nodes.insert(x);
added[x] ++;
}
ll ans = d + sum;
vector < int > attach;
for (int cur : nodes)
{
if (is_leaf[cur])
added[cur] --;
added[cur] %= 2;
if (added[cur] > 0)
{
attach.push_back(cur);
}
}
if ((sub[root] % 2 + attach.size()) % 2 == 1)
{
cout << -1 << endl;
}
else
{
cout << ans + virtual_tree(attach) << endl;
}
for (int cur : nodes)
{
added[cur] = 0;
}
}
}
void solve()
{
input();
answer_queries();
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
/**
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
3 1
1 2
1 3
6 3 3 3 2 2 2
15 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
4 4 5 3 7
*/
Compilation message
cleaning.cpp: In function 'll virtual_tree(std::vector<int>)':
cleaning.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for (int i = 1; i < nodes.size(); i ++)
| ~~^~~~~~~~~~~~~~
cleaning.cpp:225:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for (int i = 0; i < nodes.size(); i ++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12380 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
24656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21596 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21460 KB |
Output is correct |
| 3 |
Correct |
47 ms |
37204 KB |
Output is correct |
| 4 |
Correct |
79 ms |
40684 KB |
Output is correct |
| 5 |
Correct |
39 ms |
35608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
27212 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
27400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
31452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12380 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
24656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
