#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;
vector < int > nodes;
for (int j = 0; j < d; j ++)
{
int x;
cin >> x;
nodes.push_back(x);
}
ll ans = nodes.size();
for (int cur : nodes)
{
added[cur] ++;
if (added[cur] == 1 && is_leaf[cur])
continue;
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)
{
added[cur] --;
if (added[cur] == 0 && is_leaf[cur])
continue;
int v = cur;
while(v != -1)
{
sub[v] --;
v = parent[v];
}
}
}
}
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 |
1 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
100 ms |
17712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14552 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14556 KB |
Output is correct |
| 3 |
Correct |
26 ms |
26008 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24188 KB |
Output is correct |
| 5 |
Correct |
30 ms |
26200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
743 ms |
15072 KB |
Output is correct |
| 2 |
Correct |
743 ms |
15072 KB |
Output is correct |
| 3 |
Correct |
403 ms |
31592 KB |
Output is correct |
| 4 |
Execution timed out |
1037 ms |
31056 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1046 ms |
18012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1046 ms |
23304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1043 ms |
25880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
100 ms |
17712 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14552 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14556 KB |
Output is correct |
| 5 |
Correct |
26 ms |
26008 KB |
Output is correct |
| 6 |
Correct |
24 ms |
24188 KB |
Output is correct |
| 7 |
Correct |
30 ms |
26200 KB |
Output is correct |
| 8 |
Correct |
743 ms |
15072 KB |
Output is correct |
| 9 |
Correct |
743 ms |
15072 KB |
Output is correct |
| 10 |
Correct |
403 ms |
31592 KB |
Output is correct |
| 11 |
Execution timed out |
1037 ms |
31056 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
