#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;
}
void answer_queries()
{
int root = 1;
while(adj[root].size() == 1)
root ++;
calc(root, -1);
build_sparse_table();
dfs(root);
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;
for (int cur : nodes)
{
if (is_leaf[cur])
added[cur] --;
added[cur] %= 2;
if (added[cur] > 0)
{
int v = cur;
while(v != -1)
{
sub[v] ++;
v = parent[v];
}
}
}
if (sub[root] % 2 == 1)
{
cout << -1 << endl;
}
else
{
for (int i = 1; i <= n; i ++)
{
if (i == root)
continue;
if (sub[i] % 2 == 0)
ans += 2;
else
ans += 1;
}
cout << ans << endl;
}
for (int cur : nodes)
{
if (added[cur] == 0)
continue;
int v = cur;
while(v != -1)
{
sub[v] --;
v = parent[v];
}
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
98 ms |
17848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
14228 KB |
Output is correct |
| 2 |
Correct |
12 ms |
14264 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25916 KB |
Output is correct |
| 4 |
Correct |
50 ms |
26056 KB |
Output is correct |
| 5 |
Correct |
52 ms |
28616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
37 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
410 ms |
31828 KB |
Output is correct |
| 4 |
Execution timed out |
1070 ms |
32976 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1044 ms |
18192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
23380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
25748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
98 ms |
17848 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14228 KB |
Output is correct |
| 4 |
Correct |
12 ms |
14264 KB |
Output is correct |
| 5 |
Correct |
27 ms |
25916 KB |
Output is correct |
| 6 |
Correct |
50 ms |
26056 KB |
Output is correct |
| 7 |
Correct |
52 ms |
28616 KB |
Output is correct |
| 8 |
Correct |
36 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
37 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
410 ms |
31828 KB |
Output is correct |
| 11 |
Execution timed out |
1070 ms |
32976 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
