#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 sub[maxn], 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;
sub[v] = 1;
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);
sub[v] += sub[u];
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)];
}
int find_centroid(int v, int par, int sz)
{
for (int u : adj[v])
{
if (u == par)
continue;
if (sub[u] > sz / 2)
{
return find_centroid(u, v, sz);
}
}
return v;
}
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;
}
int used[maxn];
bool cmp(int v, int u)
{
return tin[v] < tin[u];
}
void answer_queries()
{
int root = 1;
while(adj[root].size() == 1)
root ++;
calc(root, -1);
build_sparse_table();
find_depths(root);
ll base = sum[root];
for (int i = 1; i <= q; i ++)
{
int d;
cin >> d;
vector < int > nodes;
for (int j = 1; j <= d; j ++)
{
int par;
cin >> par;
nodes.push_back(par);
}
if ((n <= 20000 && q <= 300) || q == 1)
{
for (int cur : nodes)
added[cur] ++;
find_depths(root);
if (cnt[root] % 2 == 1)
cout << -1 << endl;
else
cout << sum[root] << endl;
}
else
{
vector < int > attach;
ll extra_ans = 0;
for (int cur : nodes)
{
if (added[cur] == 0)
{
extra_ans ++;
}
else
{
attach.push_back(cur);
}
added[cur] ++;
}
sort(attach.begin(), attach.end(), cmp);
if (attach.size() % 2 == 1)
cout << -1 << endl;
else
{
for (int i = 0; i < attach.size(); i += 2)
{
extra_ans = extra_ans + get_distance(attach[i], attach[i + 1]) + 2;
}
cout << extra_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
3 1
1 2
1 3
6 3 3 3 2 2 2
*/
Compilation message
cleaning.cpp: In function 'void answer_queries()':
cleaning.cpp:217:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for (int i = 0; i < attach.size(); i += 2)
| ~~^~~~~~~~~~~~~~~
cleaning.cpp:170:8: warning: unused variable 'base' [-Wunused-variable]
170 | ll base = sum[root];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
17488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14556 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14556 KB |
Output is correct |
| 3 |
Correct |
30 ms |
26324 KB |
Output is correct |
| 4 |
Correct |
27 ms |
24392 KB |
Output is correct |
| 5 |
Correct |
33 ms |
26792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
17120 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17276 KB |
Output is correct |
| 3 |
Correct |
41 ms |
33548 KB |
Output is correct |
| 4 |
Correct |
44 ms |
32676 KB |
Output is correct |
| 5 |
Correct |
42 ms |
32080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
152 ms |
17244 KB |
Output is correct |
| 3 |
Correct |
193 ms |
17240 KB |
Output is correct |
| 4 |
Correct |
233 ms |
18020 KB |
Output is correct |
| 5 |
Correct |
209 ms |
18136 KB |
Output is correct |
| 6 |
Correct |
233 ms |
17756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
23124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
25972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
17488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
