KOI 城市由 $N$ 个交叉路口和 $N-1$ 条双向道路组成，任意两个不同的交叉路口之间都可以仅通过道路相互到达。也就是说，城市的道路网构成了一棵树。道路位于二维平面上，且除了端点外，任意两条道路不会相交。每条道路都有一个非负整数权重。

KOI 城市在几十年前还是一个小村庄，但随着人口流入和规模扩大，城市开始迅速扩张。在快速扩张的过程中，为了行政方便，市长给交叉路口分配了 $0$ 到 $N-1$ 之间的编号。此时，编号系统满足以下性质：

• $0$ 号交叉路口是城市的中心，保证与至少 $2$ 条道路相连。
• 交叉路口的编号是该树以 $0$ 号交叉路口为根进行先序遍历（Preorder）的顺序之一。
• 对于所有交叉路口，考虑与其相邻（直接通过道路连接）的交叉路口中编号最小的一个。以该交叉路口为基准，按逆时针方向列出相邻交叉路口的编号时，编号是递增的。

随着大量人口涌入 KOI 城市，交通拥堵问题日益严重。为了解决这个问题，市长将交通基础设施最薄弱的城市用外环道路连接起来。设 KOI 城市中所有仅与 $1$ 条道路相连的交叉路口按编号递增顺序排列的列表为 $\{V[0], V[1], \dots, V[K-1]\}$。市长为所有 $0 \le i \le K-1$ 建造了连接 $V[i]$ 号交叉路口和 $V[(i+1) \mod K]$ 号交叉路口的双向道路。每条道路的权重为非负整数 $W[i]$。值得注意的是，由于编号系统的特性，外环道路可以连接起来，且除了端点外，两条道路不会相交。

以 KOI 城市为据点的邪恶犯罪团伙 Dlalswp 给市民造成了巨大伤害。市长为了抓捕 Dlalswp 犯罪团伙，投入了情报人员。据情报人员探知，Dlalswp 犯罪团伙将长度为奇数的简单环设定为犯罪区域，并在该环内巡回进行犯罪活动。

为了抓捕臭名昭著的 Dlalswp 犯罪团伙，市长计划在 KOI 城市的道路上部署警察，使得所有长度为奇数的简单环中至少有一条部署了警察的边。在每条道路上部署警察所需的费用等于该道路的权重。请计算市长实现目标所需的最小费用。

实现细节

你需要实现以下函数：

long long place_police(vector<int> P, vector<long long> C, vector<long long> W)

• 该函数仅被调用一次。
• $P$：大小为 $N-1$ 的整数数组。表示建造外环道路前构成原 KOI 城市的道路。对于所有 $i$ ($0 \le i \le N-2$)，存在连接 $P[i]$ 号交叉路口和 $i+1$ 号交叉路口的道路。
• $C$：大小为 $N-1$ 的整数数组。对于所有 $i$ ($0 \le i \le N-2$)，连接 $P[i]$ 号交叉路口和 $i+1$ 号交叉路口的道路权重为 $C[i]$。
• $W$：大小为 $K$ 的整数数组。对于所有 $i$ ($0 \le i \le K-1$)，连接 $V[i]$ 号交叉路口和 $V[(i+1) \mod K]$ 号交叉路口的双向道路权重为 $W[i]$。
• 该函数必须返回在所有长度为奇数的简单环中至少有一条部署了警察的边的情况下，在 KOI 城市道路上部署警察的最小费用。

提交的源代码中任何部分都不得执行输入输出函数。

数据范围

• $4 \le N \le 100\,000$
• 对于所有 $i$，$0 \le P[i] \le i$ ($0 \le i \le N-2$)
• 对于所有 $i$，$0 \le C[i] \le 10^{12}$ ($0 \le i \le N-2$)
• 对于所有 $i$，$0 \le W[i] \le 10^{12}$ ($0 \le i \le K-1$)

子任务

1. (6分) $K \le 5$
2. (8分) 对于所有 $i$，$P[i] = 0$ ($0 \le i \le N-2$)
3. (5分) 对于所有 $i$，$C[i] \le 10^6$ ($0 \le i \le N-2$)，对于所有 $i$，$W[i] = 10^{12}$ ($0 \le i \le K-1$)，$K$ 为偶数
4. (15分) 对于所有 $i$，$C[i] \le 10^6$ ($0 \le i \le N-2$)，对于所有 $i$，$W[i] = 10^{12}$ ($0 \le i \le K-1$)
5. (57分) 不存在与 $4$ 条及以上道路相连的交叉路口。
6. (9分) 无额外限制。

样例

样例 1

考虑 $N = 4, P = [0, 0, 0], C = [9, 8, 0], W = [9, 9, 9]$ 的情况。

输入格式 1

4
0 9
0 8
0 0
9 9 9

输出格式 1

9

说明

KOI 城市共有 $4$ 个奇数环：$\{0, 1, 2\}, \{0, 2, 3\}, \{0, 3, 1\}, \{1, 2, 3\}$。如果市长在连接 $(0, 3)$ 权重为 $0$ 的道路和连接 $(1, 2)$ 权重为 $9$ 的道路上部署警察，则所有奇数环中都至少有一条部署了警察的道路。该部署的费用为 $0 + 9 = 9$，无法以更低的费用达成目标。

样例 2

考虑 $N = 11, P = [0, 0, 2, 3, 3, 2, 0, 7, 7, 9], C = [9, 8, 0, 7, 1, 6, 0, 7, 1, 6], W = [10^{12}, \dots, 10^{12}]$ 的情况。$W$ 的大小为 $6$，所有元素均为 $10^{12}$。

输入格式 2

11
0 9
0 8
2 0
3 7
3 1
2 6
0 0
7 7
7 1
9 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000

输出格式 2

1

说明

如果市长在连接 $(2, 3)$ 权重为 $0$ 的道路、连接 $(0, 7)$ 权重为 $0$ 的道路以及连接 $(3, 5)$ 权重为 $1$ 的道路上部署警察，则所有奇数环中都至少有一条部署了警察的道路。该部署的费用为 $0 + 0 + 1 = 1$，无法以更低的费用达成目标。