P15584 [KTSC 2026] 网格树 / Grid Tree

给定一棵 $N$ 个点的有根树，其节点编号 $0\sim N-1$。点 $0$ 是根，每个点有 $0$ 或 $2$ 个儿子。对恰有两儿子的节点，区分左儿子和右儿子。每条树边 $e$ 有正整数长度 $c_e$。 将树画在二维笛卡尔坐标系中。每个节点 $v$ 被画在不同的格点 $m_v=(x_v,y_v)$ 处。这里，根必须画在 $m_0=(0,0)$ 处。格点即 $x,y$ 坐标均为整数的点。 一条连接 $v$ 和其父亲 $p$ 的树边 $e=(p,v)$ 在坐标系中被画成一条连接 $m_p$ 和 $m_v$ 的路径。路径必须满足以下所有条件： - 沿着从 $m_p$ 到 $m_v$ 的路径移动时，运动方向必须始终为 $x$ 轴正方向或 $y$ 轴正方向。这意味着，沿 $x$ 坐标和 $y$ 坐标均递增的方向的路径不合法。此外，方向只能在格点处改变。这意味着，若一条路径长度为 $k$，方向只可能在 $(k-1)$ 个格点处改变。 - 若 $v$ 是 $p$ 的左儿子，路径从 $m_p$ 的起始方向必须沿 $x$ 轴正方向。 - 若 $v$ 是 $p$ 的右儿子，路径从 $m_p$ 的起始方向必须沿 $y$ 轴正方向。 - 路径长度至少为对应边的边长 $c_e$。 - 路径**不能相交**。换言之，一条路径的内点（即除去起终点后的所有点）不能在另一条路径上。 定义节点 $v$ 的**坐标系深度**为 $L(v)=x_v+y_v$。在画出来的树中，所有叶子（无儿子的节点）的坐标系深度必须相同。定义叶子的深度为**网格深度**。 在所有合法的画图方式中，求出**网格深度**的最小值。 ### 实现细节 **这是一道函数式交互题**。你不必，也不应实现 `main` 函数。 你应当实现以下的函数： ```cpp long long compute_min_depth(int N, vector P, vector C, vector D) ``` - $N$：节点数。 - $P,C,D$：大小为 $N-1$ 的整数数组。对于任意 $1\le i\le N-1$，点 $i$ 的父亲为 $P[i-1]$。令 $e$ 为 $i$ 与它父亲的连边，则 $c_e=C[i-1]$。若 $D[i-1]=0$，点 $i$ 为左儿子；否则 $D[i-1]=1$，点 $i$ 为右儿子。 - 可以证明，存在一种合法的画图方式。该函数应当返回合法的画图方式中，网格深度的最小值。 - 该函数被调用恰好一次。 你的源代码中不应调用任何输入/输出函数。

示例评测程序的输入格式如下： - 第 $1$ 行：$N$ - 对于所有 $0 \leq i < N - 1$： - 第 $2 + i$ 行：$P[i]$ $C[i]$ $D[i]$

示例评测程序按以下格式打印答案： - 第 $1$ 行：`compute_min_depth` 的返回值

### 数据范围 - 给定的是以点 $0$ 为根的有根树； - 每个节点的儿子数为 $0$ 或 $2$； - $3\le N\le 200\, 000$； - 对于任意 $0\le i\le N-2$，$0\le P[i]\le N-1$； - 对于任意 $0\le i\le N-2$，$1\le C[i]\le 10^9$； - 对于任意 $0\le i\le N-2$，$0\le D[i]\le 1$。 ### 子任务 定义两个节点的距离为连接这两个节点的唯一简单路的边权之和。 定义叶子为有 $0$ 个儿子的点。 | 编号 | 得分 | 限制 | | :-: | :-: | :- | | $1$ | $10$ | $N\le 7$ | | $2$ | $ 8$ | 对于任意有两个儿子的点 $v$，$v$ 的其中一个儿子是叶子 | | $3$ | $21$ | $N\le 5\,000$，所有叶子到点 $0$ 距离均为 $K$（$\le 2500$） | | $4$ | $29$ | $N\le 5\, 000$，所有节点到点 $0$ 的距离至多为 $2500$ | | $5$ | $32$ | 无额外限制 | ### 计分方式 对于子任务 $3$，若网格深度恰为 $K$ 的画图方式不存在，且 `compute_min_depth` 返回 $-1$，该测试点将被判为正确。更为精确地说： - 对于存在网格深度恰为 $K$ 的画图方式的测试点： - 若返回 $K$，得满分； - 否则，得 $0$ 分。 - 对于不存在网格深度恰为 $K$ 的画图方式的测试点： - 若返回最小网格深度，得满分； - 若返回 $-1$，得满分； - 否则，得 $0$ 分。 注意：子任务 $3$ 中，所有叶子到点 $0$ 的距离均相等，为 $K$。 ### 样例 #### 样例 $1$ 考虑以下调用： `compute_min_depth(5, [4, 0, 4, 0], [1, 2, 1, 1], [0, 1, 1, 0])` - 我们可以画出一棵网格深度为 $2$ 的树，如下图所示。 ::::align{center}  :::: 可以证明，不存在网格深度小于 $2$ 的绘图。 因此，该函数应返回 $2$。 #### 样例 $2$ 考虑以下调用： `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])` - 我们可以画出一棵网格深度为 $4$ 的树，如下图所示。 ::::align{center}  :::: 因此，该函数应返回 $4$。