P15584 [KTSC 2026] Grid Tree / Grid Tree

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: ```cpp long long compute_min_depth(int N, vector P, vector C, vector 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.

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]$.

The sample grader prints the answer in the following format: - Line $1$: the return value of `compute_min_depth`.

### 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. | ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $10$ | $N\le 7$ | | $2$ | $ 8$ | For any node $v$ with two children, one of the children of $v$ is a leaf. | | $3$ | $21$ | $N\le 5\,000$, the distances from all leaves to node $0$ are all $K$ ($\le 2500$). | | $4$ | $29$ | $N\le 5\, 000$, the distance from any node to node $0$ is at most $2500$. | | $5$ | $32$ | No additional constraints. | ### 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