题目描述

给定一棵 $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 函数。

你应当实现以下的函数：

long long compute_min_depth(int N, vector<int> P, vector <int> C, vector<int> 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 的返回值

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

提示

数据范围

• 给定的是以点 $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$。