给定一棵有根树，节点编号为 $0$ 到 $N-1$。节点 $0$ 是这棵树的根节点。每个节点的子节点数要么为 $0$，要么为 $2$。对于恰有两个子节点的节点，其子节点被指定为左子节点和右子节点。树中每条边都有一个正整数长度 $c_e$。
我们将在二维坐标平面上绘制这棵树。每个节点 $v$ 被绘制在一个互不相同的整点 $(x_v, y_v)$ 上。其中根节点必须绘制在 $(0,0)$。整点是指横纵坐标均为整数的点。
连接节点 $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$。在所绘制的树中，所有没有子节点的节点必须具有相同的深度。称该深度为网格深度（grid depth）。
请找出所有合法绘制方案中的最小网格深度。
实现细节
你需要实现以下函数：
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$ 是其父节点的右子节点。
可以证明，满足条件的树的绘制方案一定存在。函数应返回最小的网格深度。
该函数仅会被调用一次。
提交的源代码不得执行任何输入/输出函数。
限制
- 给定的边构成一棵以节点 $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$
子任务
定义树中两个节点之间的距离为连接它们的唯一简单路径上所有边长度之和。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 10 | $N \le 7$ |
| 2 | 8 | 对于每个恰有两个子节点的节点 $v$，其某一个子节点没有子节点 |
| 3 | 21 | $N \le 5000$，且对于所有没有子节点的节点 $v$，节点 $0$ 到 $v$ 的距离相同（为 $K$） |
| 4 | 29 | $N \le 5000$，且对于所有没有子节点的节点 $v$，节点 $0$ 到 $v$ 的距离至多为 $2500$ |
| 5 | 32 | 无附加限制 |
评分
对于子任务 $3$，若不存在网格深度恰为 $K$ 的树的绘制方案，当 compute_min_depth 返回 $-1$ 时也视为正确。更具体地：
- 若测试数据中存在网格深度为 $K$ 的绘制方案：
- 若返回值为 $K$，得满分；
- 否则得 $0$ 分。
- 若测试数据中不存在网格深度为 $K$ 的绘制方案：
- 若返回最小网格深度，得满分；
- 若返回 $-1$，得满分；
- 否则得 $0$ 分。
注意，在子任务 $3$ 中，对于所有没有子节点的节点 $v$，节点 $0$ 到 $v$ 的距离均相同，且该距离为 $K$。
样例数据
样例 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$。
样例交互库
样例交互库的输入格式如下：
- 第 1 行：$N$
- 对于所有 $0 \le i < N-1$：
- 第 $2+i$ 行：$P[i]\ C[i]\ D[i]$
样例交互库按如下格式输出答案：
- 第 1 行：
compute_min_depth的返回值