AdditionalFile5620.zip

#5620. 「KTSC 2026 R1」格点树

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "grid.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「격자 트리」

给定一棵包含 $N$ 个节点的有根树，节点编号为 $0$ 到 $N-1$。$0$ 号节点是该树的根，且每个节点的子节点数量均为 $0$ 或 $2$。对于子节点数量为 $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$。在我们绘制的树中，所有子节点数量为 $0$ 的节点（叶子节点）必须具有相同的深度。我们将此深度称为格点深度。

请在所有合法的树绘制方案中，求出格点深度的最小值。

实现细节

你需要实现以下函数：

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

• $N$：节点的数量。
• $P, C, D$：大小为 $N-1$ 的整数数组。对于所有 $1 \leq i \leq N-1$，$i$ 号节点的父节点是 $P[i-1]$。若连接 $i$ 号节点与其父节点的边为 $e$，则 $c_e = C[i-1]$。如果 $D[i-1] = 0$，$i$ 号节点是其父节点的左子节点；如果 $D[i-1] = 1$，$i$ 号节点是其父节点的右子节点。
• 可以证明，始终存在满足条件的树绘制方案。该函数应返回其中格点深度的最小值。
• 该函数仅会被调用一次。

在提交的源代码中，你不应在任何地方执行输入或输出函数。

样例 1

考虑以下调用： compute_min_depth(5, [4, 0, 4, 0], [1, 2, 1, 1], [0, 1, 1, 0])

• 如下所示，可以绘制一棵格点深度为 $2$ 的树。

可以证明，不存在格点深度小于 $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$ 的树。（此处图示部分由后续添加）

因此函数应返回 $4$。

数据范围与提示

对于所有输入数据，满足：

• 给定的边构成一棵以 $0$ 号节点为根的树。
• 每个节点的子节点数量为 $0$ 或 $2$。
• $3 \leq N \leq 200000$
• 对于所有 $i$，满足 $0 \leq P[i] \leq N-1$ $(0 \leq i \leq N-2)$。
• 对于所有 $i$，满足 $1 \leq C[i] \leq 10^9$ $(0 \leq i \leq N-2)$。
• 对于所有 $i$，满足 $0 \leq D[i] \leq 1$ $(0 \leq i \leq N-2)$。

定义树中两个节点之间的距离为连接这两个节点的唯一路径上所有边的长度之和。详细子任务附加限制及分值如下表所示。

在子任务 $3$ 中，如果不存在格点深度恰好为 $K$ 的树绘制方案，即使 compute_min_depth 返回 -1 也被视为正确。更准确地说：

• 在存在格点深度为 $K$ 的方案的测试用例中：
  • 返回 $K$ 获得满分。
  • 否则获得 $0$ 分。
• 在不存在格点深度为 $K$ 的方案的测试用例中：
  • 返回最小格点深度获得满分。
  • 返回 -1 获得满分。
  • 否则获得 $0$ 分。

在子任务 $3$ 中，请注意所有叶子节点 $v$ 到 $0$ 号节点的距离都是相同的，且该距离为 $K$。

示例评测程序

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

• 第一行包含一个整数 $N$。
• 对于所有 $0 \leq i < N-1$：
  • 第 $2+i$ 行包含三个整数 $P[i], C[i], D[i]$。

示例评测程序按以下格式输出答案：

• 第一行输出 compute_min_depth 的返回值。