#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const int N = 200000, infI = 1e9 + 7;
const ll infL = 3e18;
vector<int> g[N];
ll dp[3][N];//LL???
int depth[N], parent[N];
void pull(int v) {
dp[0][v] = 0;
dp[1][v] = dp[2][v] = infL;
if (sz(g[v]) <= 1) {
//v is a leaf
dp[1][v] = 1;
} else {
for (int to: g[v]) {
if (to != parent[v]) {
array<ll, 3> dq = {dp[0][v], dp[1][v], dp[2][v]};
dp[0][v] = min({dq[2] + dp[2][to], dq[1] + dp[1][to]});
dp[1][v] = min({dq[0] + dp[1][to], dq[2] + dp[1][to], dq[1] + dp[2][to]});
dp[2][v] = min({dq[0] + dp[2][to], dq[2] + dp[2][to], dq[1] + dp[1][to]});
}
}
dp[1][v] += 1;
dp[2][v] += 2;
}
}
void dfs(int v, int p) {
if (p != -1) {
depth[v] = depth[p] + 1;
}
parent[v] = p;
dp[0][v] = 0;
dp[1][v] = dp[2][v] = infL;
if (sz(g[v]) <= 1) {
//v is a leaf
dp[1][v] = 1;
} else {
for (int to: g[v]) {
if (to != p) {
dfs(to, v);
array<ll, 3> dq = {dp[0][v], dp[1][v], dp[2][v]};
dp[0][v] = min({dq[2] + dp[2][to], dq[1] + dp[1][to]});
dp[1][v] = min({dq[0] + dp[1][to], dq[2] + dp[1][to], dq[1] + dp[2][to]});
dp[2][v] = min({dq[0] + dp[2][to], dq[2] + dp[2][to], dq[1] + dp[1][to]});
}
}
dp[1][v] += 1;
dp[2][v] += 2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
int root = -1;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
int mxx = 0;
for (int i = 0; i < n; ++i) {
mxx = max(mxx, sz(g[i]));
}
for (int i = 0; i < n; ++i) {
if (sz(g[i]) > 1) {
root = i;
break;
}
}
assert(root != -1);
dfs(root, -1);
if (*max_element(all(depth)) <= 18 && mxx <= 3) {
while (q--) {
int D;
cin >> D;
vector<int> a(D);
for (int i = 0; i < D; ++i) {
cin >> a[i];
--a[i];
}
sort(all(a));
vector<int> b;
int extra = 0;
for (int i = 0; i < D;) {
int j = i;
while (j < D && a[i] == a[j])
++j;
if ((j - i) & 1) {
b.push_back(a[i]);
extra += j - i - 1;
} else {
b.push_back(a[i]);
b.push_back(a[i]);
extra += j - i - 2;
}
i = j;
}
swap(a, b);
D = sz(a);
for (int i = 0; i < D; ++i) {
g[a[i]].push_back(i + n);
}
for (int i = 0; i < D; ++i) {
pull(i + n);
if (i == D - 1 || a[i + 1] != a[i]) {
int x = a[i];
while (x != -1) {
pull(x);
x = parent[x];
}
}
}
cout << (dp[0][root] >= infL ? -1 : dp[0][root] + extra) << '\n';
for (int i = 0; i < D; ++i) {
g[a[i]].pop_back();
if (i == D - 1 || a[i + 1] != a[i]) {
int x = a[i];
while (x != -1) {
pull(x);
x = parent[x];
}
}
}
}
} else {
while (q--) {
int D;
cin >> D;
vector<int> a(D);
for (int i = 0; i < D; ++i) {
cin >> a[i];
--a[i];
}
for (int i = 0; i < D; ++i) {
g[a[i]].push_back(i + n);
}
dfs(root, -1);
cout << (dp[0][root] >= infL ? -1 : dp[0][root]) << '\n';
for (int i = 0; i < D; ++i) {
g[a[i]].pop_back();
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
1079 ms |
6504 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8532 KB |
Output is correct |
| 3 |
Correct |
30 ms |
11852 KB |
Output is correct |
| 4 |
Correct |
54 ms |
14016 KB |
Output is correct |
| 5 |
Correct |
65 ms |
16164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
9172 KB |
Output is correct |
| 2 |
Correct |
22 ms |
9160 KB |
Output is correct |
| 3 |
Correct |
58 ms |
19044 KB |
Output is correct |
| 4 |
Correct |
67 ms |
21148 KB |
Output is correct |
| 5 |
Correct |
52 ms |
17696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
7044 KB |
Output is correct |
| 2 |
Correct |
199 ms |
6500 KB |
Output is correct |
| 3 |
Correct |
245 ms |
6320 KB |
Output is correct |
| 4 |
Correct |
337 ms |
6908 KB |
Output is correct |
| 5 |
Correct |
262 ms |
7032 KB |
Output is correct |
| 6 |
Correct |
342 ms |
7008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
9360 KB |
Output is correct |
| 2 |
Correct |
169 ms |
9384 KB |
Output is correct |
| 3 |
Correct |
163 ms |
7324 KB |
Output is correct |
| 4 |
Correct |
199 ms |
9304 KB |
Output is correct |
| 5 |
Correct |
200 ms |
9356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
11412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
1079 ms |
6504 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
