#215487. [KTSC 2026] 网格树 / Grid Tree

给定一棵 个点的有根树，其节点编号 。点 是根，每个点有 或 个儿子。对恰有两儿子的节点，区分左儿子和右儿子。每条树边 有正整数长度 。

将树画在二维笛卡尔坐标系中。每个节点 被画在不同的格点 处。这里，根必须画在 处。格点即 坐标均为整数的点。

一条连接 和其父亲 的树边 在坐标系中被画成一条连接 和 的路径。路径必须满足以下所有条件：

• 沿着从 到 的路径移动时，运动方向必须始终为 轴正方向或 轴正方向。这意味着，沿 坐标和 坐标均递增的方向的路径不合法。此外，方向只能在格点处改变。这意味着，若一条路径长度为 ，方向只可能在 个格点处改变。
• 若 是 的左儿子，路径从 的起始方向必须沿 轴正方向。
• 若 是 的右儿子，路径从 的起始方向必须沿 轴正方向。
• 路径长度至少为对应边的边长 。
• 路径不能相交。换言之，一条路径的内点（即除去起终点后的所有点）不能在另一条路径上。

定义节点 的坐标系深度为 。在画出来的树中，所有叶子（无儿子的节点）的坐标系深度必须相同。定义叶子的深度为网格深度。

在所有合法的画图方式中，求出网格深度的最小值。

实现细节

这是一道函数式交互题。你不必，也不应实现 main 函数。

你应当实现以下的函数：

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

• ：节点数。
• ：大小为 的整数数组。对于任意 ，点 的父亲为 。令 为 与它父亲的连边，则 。若 ，点 为左儿子；否则 ，点 为右儿子。
• 可以证明，存在一种合法的画图方式。该函数应当返回合法的画图方式中，网格深度的最小值。
• 该函数被调用恰好一次。

你的源代码中不应调用任何输入/输出函数。

示例评测程序的输入格式如下：

• 第 行：
• 对于所有 ：
  • 第 行：

示例评测程序按以下格式打印答案：

• 第 行：compute_min_depth 的返回值

样例输入 1

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

样例输出 1

2

样例输入 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

样例输出 2

4

数据范围

• 给定的是以点 为根的有根树；
• 每个节点的儿子数为 或 ；
• ；
• 对于任意 ，；
• 对于任意 ，；
• 对于任意 ，。

子任务

定义两个节点的距离为连接这两个节点的唯一简单路的边权之和。

定义叶子为有 个儿子的点。

计分方式

对于子任务 ，若网格深度恰为 的画图方式不存在，且 compute_min_depth 返回 ，该测试点将被判为正确。更为精确地说：

• 对于存在网格深度恰为 的画图方式的测试点：
  • 若返回 ，得满分；
  • 否则，得 分。
• 对于不存在网格深度恰为 的画图方式的测试点：
  • 若返回最小网格深度，得满分；
  • 若返回 ，得满分；
  • 否则，得 分。

注意：子任务 中，所有叶子到点 的距离均相等，为 。

样例

样例

考虑以下调用：

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

• 我们可以画出一棵网格深度为 的树，如下图所示。

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

可以证明，不存在网格深度小于 的绘图。

因此，该函数应返回 。

样例

考虑以下调用：

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])

• 我们可以画出一棵网格深度为 的树，如下图所示。 ::::align{center} ::::

因此，该函数应返回 。