#include #include #include using namespace std; struct Node { vector childIndices; int parent = -1; long long value = -1; int level = -1; int index; bool valueUsed = false; }; vector nodes; void fillLevels(Node *node) { // If we have no children, or level = 1 if (node->childIndices.size() == 0) { node->level = 1; } else { // Our level is the max of our children + 1 int m = -1; // First, fill the level of all children for (auto i = 0; i < node->childIndices.size(); i++) { auto child = nodes[node->childIndices[i]]; fillLevels(child); m = max(m, child->level); } node->level = m + 1; } } void printTree(vector nodes) { return; for (auto i = 0; i < nodes.size(); i++) { auto node = nodes[i]; cout << "Node " << node->index << " has value " << node->value << ", level " << node->level << " and parent " << node->parent << endl; } cout << endl << endl; } int main() { int n, k; cin >> n >> k; vector skills; for (auto i = 0; i < k; i++) { int p; cin >> p; skills.push_back(p); } auto root = new Node; root->index = 0; nodes.push_back(root); sort(skills.begin(), skills.end(), greater()); for (auto i = 1; i < n; i++) { auto node = new Node; node->index = i; cin >> node->parent; nodes[node->parent]->childIndices.push_back(i); nodes.push_back(node); } fillLevels(root); printTree(nodes); auto sortedNodes = nodes; sort(sortedNodes.begin(), sortedNodes.end(), [](Node *a, Node *b) { return a->level > b->level; }); // First, place the best skill at the root root->value = skills[0]; int skillIndex = 1; for (auto i = 1; i < sortedNodes.size(); i++) { auto node = sortedNodes[i]; auto parent = nodes[node->parent]; if (parent->valueUsed) { // If the parent value is used, pick the next skill node->value = skills[skillIndex]; skillIndex++; } else { // If the parent value is not used, use it parent->valueUsed = true; node->value = parent->value; } } unsigned long long sum = 0; // Get sum, but skip root for (auto i = 1; i < nodes.size(); i++) { sum += nodes[i]->value; } cout << sum << endl; return 0; }