This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
struct node {
int num = -2;
vector<node*> conns;
};
node empty_node;
int check_subtree(node* root, int parent_num) {
int ans = 0;
int odd_children_num = 0;
for (auto child : root->conns) {
if (child->num == parent_num) continue;
int child_cost = check_subtree(child, root->num);
if (child_cost >= 0) {
ans += (child_cost + 1);
odd_children_num++;
}
else ans += (2 - child_cost);
}
if (odd_children_num % 2 == 1) return ans;
else return -ans;
}
void answer(node* root) {
if (root->conns.size() == 1) {
if (root->conns[0]->conns.size() == 1) cout << 1 << endl;
else answer(root->conns[0]);
return;
}
int total_cost = check_subtree(root, -1);
if (total_cost < 0) cout << -total_cost;
else cout << -1;
cout << endl;
}
int main()
{
int n, q;
cin >> n >> q;
vector<node> vec(n);
int a, b;
vec[0].num = 0;
for (int i = 1; i < n; i++) {
vec[i].num = i;
cin >> a >> b;
a--; b--;
vec[a].conns.push_back(&vec[b]);
vec[b].conns.push_back(&vec[a]);
}
int new_num;
for (int i = 0; i < q; i++) {
cin >> new_num;
vector<int> added;
for (int j = 0; j < new_num; j++) {
cin >> a; a--;
added.push_back(a);
vec[a].conns.push_back(&empty_node);
}
answer(&vec[0]);
for (int i : added) {
vec[i].conns.erase(vec[i].conns.begin() + vec[i].conns.size() - 1);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |