Police Deployment on Odd Cycles

KOI City consists of N intersections and N-1 bidirectional roads forming a tree, and its roads lie on a plane so that apart from endpoints no two roads intersect. Each road has a non‐negative cost. Many years ago the mayor numbered the intersections from 0 to N-1 in such a way that:

• Intersection 0 is the center and is adjacent to at least two roads.
• The numbering forms one of the pre‐order traversals of the tree rooted at 0.
• For every intersection, when considering its adjacent intersections (i.e. those directly connected) the one with the smallest number is listed first and then the others in counterclockwise order with increasing numbers.

Over time the city expanded so that many intersections (initially a small village) became leaves (intersections with only one incident road). Let V[0], V[1], …, V[K-1] be the list of leaves arranged in increasing order. To ease traffic congestion, the mayor plans to build an external ring road connecting the leaves: for each i (0 ≤ i ≤ K-1) a road is built between V[i] and V[(i+1) mod K] with a non‐negative weight W[i]. By the numbering property these added roads do not intersect except at endpoints.

An evil criminal gang, Dlalswp, uses a simple cycle of odd length (that is, a cycle consisting of an odd number of edges) as their crime region. In order to arrest the gang the mayor decides to deploy police on every odd cycle in the city. When police are deployed on a road, the cost incurred equals the weight of that road. In other words, we must choose a set of roads (possibly from both the original tree and the ring) with minimum total cost such that every simple cycle with an odd number of edges contains at least one police‐deployed road.

Observation: Since a tree is bipartite, its unique 2‐coloring (up to swapping) is fixed. In the graph obtained by adding the ring road, any odd simple cycle must arise from a ring edge connecting two leaves of the same color – because the unique tree path between them has even length, plus one extra edge makes an odd cycle. Thus, for every ring edge connecting leaves u and v with color(u) = color(v) (a bad ring edge), consider the unique cycle formed by that ring edge and the tree path between u and v. To counter the gang’s activity on that cycle, at least one road on the cycle must have police.

For a bad ring edge between V[i] and V[(i+1) mod K], you have two kinds of candidate roads to cover the cycle:

• The ring road itself, with cost W[i].
• At least one of the tree roads along the unique tree path between V[i] and V[(i+1) mod K]. Note that every leaf has exactly one incident tree edge. Hence, if V[i] (or V[(i+1) mod K]) is incident with a tree road of cost T(V[i]), selecting that road covers every odd cycle that uses this leaf’s incident road.

Your task is to design an algorithm that selects a set of roads (from the tree and/or the ring) with minimum total cost so that for every bad ring edge (i.e. every odd cycle) at least one road along its cycle is chosen.

Function Signature (C++):

long long place_police(vector P, vector C, vector W);

Input Description:

The function place_police will be called exactly once with three parameters:

• P: an integer array of size N-1 representing the original tree roads. For each i (0 ≤ i ≤ N-2), there is a road connecting P[i] and i+1.
• C: a long long array of size N-1 where the road connecting P[i] and i+1 has weight C[i].
• W: a long long array of size K representing the weights of the external ring roads connecting V[i] and V[(i+1) mod K] for each i (0 ≤ i ≤ K-1), where V is the list of leaves in sorted order.

Output Description:

The function should return a long long representing the minimum total cost required for deploying police such that every odd simple cycle (arising from a bad ring edge) has at least one road with police.

Note: Your solution code must not contain any input/output operations.

inputFormat

The input is provided in the following order:

1. An integer N denoting the number of intersections in the city.
2. An array P of N-1 integers (space-separated) representing the original tree roads. The i-th element corresponds to the parent of node i+1.
3. An array C of N-1 integers (space-separated) where C[i] is the weight of the road between P[i] and i+1.
4. An array W of K integers (space-separated) representing the weights of the external ring roads connecting consecutive leaves (in sorted order), where K is the number of leaves in the tree (nodes with degree 1, excluding node 0 if it happens to be degree 1).

Example:

5
0 0 1 1
3 2 4 1
0 5 0

This corresponds to a tree with N = 5 nodes, where P = [0, 0, 1, 1] and C = [3, 2, 4, 1]. The leaves (in sorted order) are [2, 3, 4] and the ring weights W = [0, 5, 0].

outputFormat

The output is a single integer (of type long long) representing the minimum total cost required so that every odd cycle in the graph (formed by a bad ring edge and the corresponding tree path) contains at least one road with police.

Example:

1

For the sample input above, the optimal solution is to deploy police on the tree road incident to leaf 4 (cost 1) thereby covering the only odd cycle (formed by leaves 3 and 4).

sample

5
0 0 1 1
3 2 4 1
0 5 0

1