#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], children[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;
children[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 <= (timer - (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[v] << " " << sum[v] << endl;
}
int used[maxn];
bool cmp(int v, int u)
{
return tin[v] < tin[u];
}
vector < int > vir[maxn];
ll cnt_on[maxn];
pair < ll, ll > vir_dfs(int v)
{
ll cnt = 0, sum = 0;
for (int u : vir[v])
{
pair < ll, ll > res = vir_dfs(u);
cnt += res.second;
sum += res.first;
}
cnt = cnt + cnt_on[v];
sum = sum + cnt_on[v] * depth[v];
ll pair = cnt / 2;
cnt -= pair * 2;
sum = sum - (ll)2 * pair * depth[v];
///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]).first;
for (int cur : nodes)
cnt_on[cur] = 0;
return ans;
}
void answer_queries()
{
int root = 1;
while(adj[root].size() == 1)
root ++;
calc(root, -1);
int cnt_leaves = 0;
for (int i = 1; i <= n; i ++)
cnt_leaves += is_leaf[i];
int special = -1;
if (cnt_leaves % 2 == 1)
{
int ver = 1;
while(!is_leaf[ver])
ver ++;
int last = ver;
int st = parent[ver];
while(children[st] == 1)
{
last = st;
st = parent[st];
}
int pt = 0;
while(adj[st][pt] != last)
pt ++;
adj[st].erase(adj[st].begin() + pt);
children[st] --;
special = ver;
parent[ver] = st;
}
build_sparse_table();
find_depths(root);
///cout << sum[1] << " : " << cnt[1] << endl;
for (int i = 1; i <= q; i ++)
{
int d;
cin >> d;
unordered_set < int > nodes;
for (int j = 0; j < d; j ++)
{
int x;
cin >> x;
nodes.insert(x);
added[x] ++;
}
ll ans = sum[root];
vector < int > attach;
for (int cur : nodes)
{
if (is_leaf[cur])
{
if (cur != special)
{
ans ++;
added[cur] --;
ll pairs = added[cur] / 2;
added[cur] -= pairs * 2;
ans = ans + pairs * 2;
///cout << "here" << added[cur] << endl;
if (added[cur] > 0)
attach.push_back(cur);
ans += added[cur];
}
}
else
{
ll pairs = added[cur] / 2;
added[cur] -= pairs * 2;
ans = ans + pairs * 2;
if (added[cur] > 0)
attach.push_back(cur);
ans += added[cur];
}
}
/**if (special != -1)
{
if (added[special] == 0)
{
attach.push_back(parent[special]);
ans = ans + depth[special] - depth[parent[special]];
}
else
{
attach.push_back(parent[special]);
ans = ans + depth[special]
}
}*/
if (attach.size() % 2 == 1)
{
cout << -1 << endl;
}
else
{
ans = ans + virtual_tree(attach);
cout << ans << 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
7 1
1 2
1 3
2 4
2 5
3 6
3 7
8 4 4 5 5 6 6 7 7
*/
Compilation message
cleaning.cpp: In function 'll virtual_tree(std::vector<int>)':
cleaning.cpp:179:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for (int i = 1; i < nodes.size(); i ++)
| ~~^~~~~~~~~~~~~~
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 = 0; i < nodes.size(); i ++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
21336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
43 ms |
38224 KB |
Output is correct |
| 4 |
Correct |
69 ms |
41456 KB |
Output is correct |
| 5 |
Correct |
37 ms |
36688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
25176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
28760 KB |
Output is correct |
| 2 |
Incorrect |
70 ms |
29020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
30800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
24584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
