#include #include #include #include #include #include using int64 = std::int64_t; namespace { constexpr int64 INF = std::numeric_limits::max() / 4; int n; std::vector weight; std::vector depth; std::vector> children; std::vector> subtree; std::vector>> states; std::vector dp; std::vector minimum_one; std::vector minimum_two; int64& value(int first, int second) { return dp[static_cast(first) * (n + 1) + second]; } void relax(int64& target, int64 candidate) { if (candidate < target) target = candidate; } void prepare(int vertex) { subtree[vertex].push_back(vertex); for (int child : children[vertex]) { depth[child] = depth[vertex] + 1; prepare(child); subtree[vertex].insert(subtree[vertex].end(), subtree[child].begin(), subtree[child].end()); } for (int other : subtree[vertex]) { states[vertex].push_back({vertex, other}); if (other != vertex) states[vertex].push_back({other, vertex}); } if (children[vertex].size() == 2) { int left = children[vertex][0]; int right = children[vertex][1]; for (int u : subtree[left]) { for (int v : subtree[right]) { states[vertex].push_back({u, v}); states[vertex].push_back({v, u}); } } } } void solve_subtree(int vertex) { if (children[vertex].empty()) { value(vertex, vertex) = weight[vertex]; return; } for (int child : children[vertex]) solve_subtree(child); if (children[vertex].size() == 1) { int child = children[vertex][0]; for (auto [v, i] : states[child]) { relax(value(vertex, v), value(i, v) + weight[vertex]); int u = v; relax(value(u, vertex), value(u, i) + weight[vertex] * (depth[i] - depth[vertex]) + weight[u]); } return; } int left = children[vertex][0]; int right = children[vertex][1]; for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF; // The outgoing original weight is in one child, and the incoming weight // finishes in the other child. for (auto [j, k] : states[left]) relax(minimum_one[k], value(j, k)); for (auto [j, k] : states[right]) relax(minimum_one[k], value(j, k)); for (auto [i, k] : states[vertex]) { if (i != vertex && k != vertex && minimum_one[k] < INF) relax(minimum_two[i], weight[i] * (depth[k] - depth[vertex]) + minimum_one[k]); } for (auto [v, i] : states[left]) relax(value(vertex, v), weight[vertex] + value(i, v) + minimum_two[i]); for (auto [v, i] : states[right]) relax(value(vertex, v), weight[vertex] + value(i, v) + minimum_two[i]); for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF; for (auto [j, k] : states[left]) relax(minimum_one[j], value(j, k) + weight[vertex] * (depth[k] - depth[vertex])); for (auto [j, k] : states[right]) relax(minimum_one[j], value(j, k) + weight[vertex] * (depth[k] - depth[vertex])); for (auto [i, j] : states[vertex]) { if (i != vertex && j != vertex && minimum_one[j] < INF) relax(minimum_two[i], weight[j] * (depth[i] - depth[vertex]) + minimum_one[j]); } for (auto [u, i] : states[left]) relax(value(u, vertex), weight[u] + value(u, i) + minimum_two[i]); for (auto [u, i] : states[right]) relax(value(u, vertex), weight[u] + value(u, i) + minimum_two[i]); for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF; for (auto [u, i] : states[left]) { relax(minimum_one[u], value(u, i) + weight[vertex] * (depth[i] - depth[vertex]) + weight[u]); relax(minimum_two[i], value(u, i)); } for (auto [u, i] : states[right]) { relax(minimum_one[u], value(u, i) + weight[vertex] * (depth[i] - depth[vertex]) + weight[u]); relax(minimum_two[i], value(u, i)); } for (auto [u, v] : states[vertex]) { if (u != vertex && v != vertex) relax(value(u, v), minimum_one[u] + minimum_two[v]); } } } // namespace int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n; weight.assign(n + 1, 0); depth.assign(n + 1, 0); children.assign(n + 1, {}); subtree.assign(n + 1, {}); states.assign(n + 1, {}); minimum_one.assign(n + 1, INF); minimum_two.assign(n + 1, INF); dp.assign(static_cast(n + 1) * (n + 1), INF); for (int i = 1; i <= n; ++i) std::cin >> weight[i]; for (int i = 2; i <= n; ++i) { int parent; std::cin >> parent; children[parent].push_back(i); } if (n == 1) { std::cout << 0 << '\n'; return 0; } prepare(1); for (int child : children[1]) solve_subtree(child); int64 answer = INF; if (children[1].size() == 1) { int child = children[1][0]; for (auto [u, v] : states[child]) relax(answer, value(u, v) + weight[1] * (depth[v] - depth[1])); } else { int first_child = children[1][0]; int second_child = children[1][1]; for (int direction = 0; direction < 2; ++direction) { std::fill(minimum_one.begin(), minimum_one.end(), INF); std::fill(minimum_two.begin(), minimum_two.end(), INF); for (auto [i, j] : states[first_child]) relax(minimum_one[i], value(i, j) + weight[1] * (depth[j] - depth[1])); for (auto [k, l] : states[second_child]) relax(minimum_two[l], value(k, l)); for (auto [i, l] : states[1]) { if (i != 1 && l != 1) relax(answer, minimum_one[i] + minimum_two[l] + weight[i] * (depth[l] - depth[1])); } std::swap(first_child, second_child); } } std::cout << answer << '\n'; return 0; }