Problem Description

You are given a rooted tree with $N$ nodes, numbered $0 \sim N-1$. Node $0$ is the root. Each node has either $0$ or $2$ children. For a node with exactly two children, its left child and right child are distinguished. Each tree edge $e$ has a positive integer length $c_e$.

Draw the tree on a 2D Cartesian coordinate system. Each node $v$ is drawn at a distinct grid point $m_v=(x_v,y_v)$. Here, the root must be drawn at $m_0=(0,0)$. A grid point is a point whose $x$ and $y$ coordinates are both integers.

A tree edge $e=(p,v)$ connecting $v$ and its parent $p$ is drawn as a path connecting $m_p$ and $m_v$ in the coordinate system. The path must satisfy all of the following conditions:

• While moving along the path from $m_p$ to $m_v$, the moving direction must always be the positive direction of the $x$ axis or the positive direction of the $y$ axis. This means that a path moving in a direction where both $x$ and $y$ increase is not allowed. Also, the direction can only change at grid points. This means that if a path has length $k$, the direction can change at only $(k-1)$ grid points.
• If $v$ is the left child of $p$, the initial direction of the path from $m_p$ must be along the positive $x$ axis.
• If $v$ is the right child of $p$, the initial direction of the path from $m_p$ must be along the positive $y$ axis.
• The path length is at least the edge length $c_e$.
• Paths must not intersect. In other words, an interior point of one path (that is, all points except its endpoints) cannot lie on another path.

Define the coordinate depth of a node $v$ as $L(v)=x_v+y_v$. In the drawn tree, all leaves (nodes with no children) must have the same coordinate depth. Define this depth of leaves as the grid depth.

Among all valid drawings, find the minimum possible value of the grid depth.

Implementation Details

This is a functional interactive problem. You do not need to, and must not, implement the main function.

You should implement the following function:

long long compute_min_depth(int N, vector<int> P, vector <int> C, vector<int> D)

• $N$: the number of nodes.
• $P,C,D$: integer arrays of size $N-1$. For any $1\le i\le N-1$, the parent of node $i$ is $P[i-1]$. Let $e$ be the edge connecting $i$ and its parent, then $c_e=C[i-1]$. If $D[i-1]=0$, node $i$ is a left child; otherwise, if $D[i-1]=1$, node $i$ is a right child.
• It can be proven that there exists a valid drawing. This function should return the minimum grid depth among valid drawings.
• This function is called exactly once.

Your source code must not call any input/output functions.

Input Format

The input format of the sample grader is as follows:

• Line $1$: $N$.
• For all $0 \leq i < N - 1$:
  • Line $2 + i$: $P[i]$ $C[i]$ $D[i]$.

Output Format

The sample grader prints the answer in the following format:

• Line $1$: the return value of compute_min_depth.

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

2

9
0 2 0
0 1 1
1 1 0
1 1 1
2 1 0
2 1 1
5 1 0
5 1 1

4

Hint

Constraints

• The given structure is a rooted tree with node $0$ as the root.
• Each node has $0$ or $2$ children.
• $3\le N\le 200\, 000$.
• For any $0\le i\le N-2$, $0\le P[i]\le N-1$.
• For any $0\le i\le N-2$, $1\le C[i]\le 10^9$.
• For any $0\le i\le N-2$, $0\le D[i]\le 1$.

Subtasks

Define the distance between two nodes as the sum of edge weights on the unique simple path connecting them.

Define a leaf as a node with $0$ children.

Scoring

For subtask $3$, if no drawing with grid depth exactly $K$ exists and compute_min_depth returns $-1$, then the test will be judged correct. More precisely:

• For testdata where a drawing with grid depth exactly $K$ exists:
  • If it returns $K$, you get full score.
  • Otherwise, you get $0$ points.
• For testdata where no drawing with grid depth exactly $K$ exists:
  • If it returns the minimum grid depth, you get full score.
  • If it returns $-1$, you get full score.
  • Otherwise, you get $0$ points.

Note: In subtask $3$, the distances from all leaves to node $0$ are equal and are $K$.

Samples

Sample $1$

Consider the following call:

compute_min_depth(5, [4, 0, 4, 0], [1, 2, 1, 1], [0, 1, 1, 0])

• We can draw a tree with grid depth $2$, as shown in the figure below.

::::align{center} ::::

It can be proven that no drawing with grid depth less than $2$ exists.

Therefore, this function should return $2$.

Sample $2$

Consider the following call:

compute_min_depth(9, [0, 0, 1, 1, 2, 2, 5, 5], [2, 1, 1, 1, 1, 1, 1, 1], [0, 1, 0, 1, 0, 1, 0, 1])

• We can draw a tree with grid depth $4$, as shown in the figure below. ::::align{center} ::::

Therefore, this function should return $4$.

Translated by ChatGPT 5