Overview

This problem involves optimizing the assignment of road construction along a tree-structured road network with waterways. For each road, we must decide which of its two endpoints (settlements) will be responsible for the construction, minimizing the total additional cost incurred.

By leveraging the properties of the tree structure and using Tree DP (Dynamic Programming on Trees), processing states from the leaves (terminal settlements) toward the root (central settlement), we can solve this efficiently.

---

Analysis

1. Structure of Decision Making

Each road (edge) is handled by exactly one of the two settlements it connects. In the tree structure, focusing on a settlement \(i\) (other than the root), the related roads can be classified into two types: 1. The road connecting to the parent settlement \(P_i\) (exactly 1) 2. Roads connecting to child settlements (0 or more)

We consider the optimal assignment within the subtree rooted at settlement \(i\). The situation of settlement \(i\) changes depending on whether the road to parent settlement \(P_i\) is “handled by the parent” or “handled by the child (settlement \(i\)).”

Therefore, we define a DP (Dynamic Programming) with two states as follows:

• \(\text{dp0}[i]\): The minimum additional cost in subtree \(i\) when the road to the parent is handled by the parent \(P_i\).
  • In this case, the roads handled by settlement \(i\) are only “roads to child settlements.”
• \(\text{dp1}[i]\): The minimum additional cost in subtree \(i\) when the road to the parent is handled by child \(i\).
  • In this case, the roads handled by settlement \(i\) are “roads to child settlements” plus “the road to the parent (1 road).”

2. Optimizing Assignment with Child Settlements

Let the child settlements of settlement \(i\) be \(v_1, v_2, \ldots, v_k\). For the road connecting settlement \(i\) and each child settlement \(v\), we decide which one handles it.

• If child settlement \(v\) handles it: The additional cost of subtree \(v\) is \(\text{dp1}[v]\).
• If settlement \(i\) handles it: The additional cost of subtree \(v\) is \(\text{dp0}[v]\). Also, the number of roads handled by settlement \(i\) increases by 1.

When switching the road to child settlement \(v\) from “handled by child \(v\)” to “handled by settlement \(i\),” the cost difference on the subtree \(v\) side is \(\text{dp0}[v] - \text{dp1}[v]\).

When settlement \(i\) decides to handle \(x\) roads (\(0 \leq x \leq k\)) among the roads to child settlements, to minimize cost, the optimal strategy is to prioritize selecting the \(x\) child settlements with the smallest difference \(\text{dp0}[v] - \text{dp1}[v]\) to be handled by settlement \(i\).

3. Specific Transitions

For all child settlements, compute the difference \(D_v = \text{dp0}[v] - \text{dp1}[v]\), and sort in ascending order. Let \(S\) be the prefix sum of the sorted differences (\(S[x]\) is the sum of the \(x\) smallest differences).

The cost when settlement \(i\) handles \(x\) roads to child settlements can be expressed as follows:

• For \(\text{dp0}[i]\) (parent handles the road to parent) The number of roads handled by settlement \(i\) is \(x\). $\(\text{Cost} = \sum_{v} \text{dp1}[v] + S[x] + W_i \times \max(0, x - C_i)\)$

• For \(\text{dp1}[i]\) (child \(i\) handles the road to parent) The number of roads handled by settlement \(i\) is \(x + 1\) (including the road to the parent). $\(\text{Cost} = \sum_{v} \text{dp1}[v] + S[x] + W_i \times \max(0, x + 1 - C_i)\)$

By exhaustively searching \(x\) from \(0\) to \(k\) and finding the minimum for each, we can determine \(\text{dp0}[i]\) and \(\text{dp1}[i]\).

---

Algorithm

1. Graph Construction: Record the parent-child relationships for each settlement. Due to the constraint \(P_i \leq i - 1\), by simply looping in decreasing order of vertex number (from \(N\) to \(1\)), we can automatically process in bottom-up order from leaves to root, without needing topological sort or DFS (Depth-First Search).

2. Compute DP Values from Leaves Upward: For each settlement \(i\):

   • Create a difference array diffs (\(\text{dp0}[v] - \text{dp1}[v]\)) from the DP values of child settlements, and sort it in ascending order.
   • Compute the prefix sum \(S\) of diffs.
   • Exhaustively search over \(x \in [0, k]\) to find the minimum values of \(\text{dp0}[i]\) and \(\text{dp1}[i]\).

3. Output the Answer: Since the root (settlement \(1\)) has no parent, the minimum additional cost is \(\text{dp0}[1]\). Adding the base construction cost \(N - 1\) to this gives the overall minimum total cost.

---

Complexity

• Time Complexity: \(O(N \log N)\) For each settlement \(i\), let \(k_i\) be the number of children. Sorting the difference array takes \(O(k_i \log k_i)\) time. Since the total number of children across all settlements is \(N - 1\), the total time for all sorting operations is at most \(O(N \log N)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N)\) The memory required to store the tree’s adjacency list, the DP tables (dp0, dp1), and the temporary arrays used at each step (diffs and prefix sums) is \(O(N)\).

---

Implementation Notes

• Be careful with types: Since the additional cost coefficient \(W_i\) can be up to \(10^9\), the total cost can easily exceed the range of int (32-bit integer). Therefore, long long (64-bit integer) must be used for the DP tables and prefix sum calculations.

• Initial value for infinity: The initial value (INF) used when finding the minimum should be set to a sufficiently large value (such as 4e18).

• Simplification of bottom-up processing: By utilizing the constraint \(P_i < i\), simply looping in reverse order with for (int i = N; i >= 1; --i) provides a concise and efficient implementation of the leaf-to-root transitions.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> P(N + 1);
    vector<vector<int>> children(N + 1);
    for (int i = 2; i <= N; ++i) {
        cin >> P[i];
        children[P[i]].push_back(i);
    }

    vector<long long> C(N + 1), W(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> C[i] >> W[i];
    }

    // dp0[i] corresponds to dp[i][0]
    // dp1[i] corresponds to dp[i][1]
    vector<long long> dp0(N + 1, 0), dp1(N + 1, 0);

    // Process bottom-up from leaves to root
    for (int i = N; i >= 1; --i) {
        int k = children[i].size();
        vector<long long> diffs;
        diffs.reserve(k);
        long long sum_dp1 = 0;
        for (int child : children[i]) {
            sum_dp1 += dp1[child];
            diffs.push_back(dp0[child] - dp1[child]);
        }
        sort(diffs.begin(), diffs.end());
        
        vector<long long> S(k + 1, 0);
        for (int j = 0; j < k; ++j) {
            S[j + 1] = S[j] + diffs[j];
        }

        long long min0 = 4e18; // Use a sufficiently large value for infinity
        long long min1 = 4e18;
        for (int x = 0; x <= k; ++x) {
            long long val0 = S[x] + W[i] * max(0LL, (long long)x - C[i]);
            if (val0 < min0) min0 = val0;
            long long val1 = S[x] + W[i] * max(0LL, (long long)x + 1 - C[i]);
            if (val1 < min1) min1 = val1;
        }
        dp0[i] = sum_dp1 + min0;
        dp1[i] = sum_dp1 + min1;
    }

    // The total cost is the minimum additional cost at the root + the base cost (N - 1)
    long long ans = dp0[1] + (N - 1);
    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.