#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N = 2e5+7;
vector <vector <int>> graph(N), new_graph(N);
int root, subtree[N];
ll ans;
void dfs(int v, int p) {
subtree[v] = (sz(new_graph[v]) == 1 ? 1 : 0);
for (auto to : new_graph[v]) {
if (to == p) {
continue;
}
dfs(to, v);
subtree[v] += subtree[to];
}
ans += 2 - (subtree[v] % 2);
}
int get(int n) {
ans = 0;
for (int i = 1; i <= n; i++) {
if (sz(new_graph[i]) > 1) {
root = i;
}
}
dfs(root, root);
if (subtree[root]&1) return -1;
else return ans-2;
}
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
graph[a].pb(b);
graph[b].pb(a);
}
if (n <= 20000 && q <= 300) {
while (q--) {
int vertex = n+1;
int k;
cin >> k;
for (int i = 1; i <= n+k; i++) {
new_graph[i].clear();
for (auto to : graph[i]) new_graph[i].pb(to);
}
while (k--) {
int x;
cin >> x;
new_graph[x].pb(vertex);
new_graph[vertex].pb(x);
vertex++;
}
cout << get(vertex-1) << endl;
}
}
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Incorrect |
11 ms |
10276 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
13212 KB |
Output is correct |
2 |
Correct |
29 ms |
13132 KB |
Output is correct |
3 |
Incorrect |
30 ms |
13180 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
13780 KB |
Output is correct |
2 |
Correct |
23 ms |
13780 KB |
Output is correct |
3 |
Incorrect |
35 ms |
12792 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
11564 KB |
Output is correct |
2 |
Correct |
217 ms |
11652 KB |
Output is correct |
3 |
Correct |
313 ms |
11300 KB |
Output is correct |
4 |
Correct |
334 ms |
11788 KB |
Output is correct |
5 |
Correct |
325 ms |
11672 KB |
Output is correct |
6 |
Correct |
339 ms |
12380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
11668 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
52 ms |
12844 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Incorrect |
11 ms |
10276 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |