题目背景

请勿使用 C++14 (GCC 9) 提交。

请在程序开头加入如下代码：

#include<vector>
long long place_police(std::vector<int> P, std::vector<long long> C, std::vector<long long> W);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2 「외곽 순환 도로 2」

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

KOI 城市几十年前还是一个小村庄，但随着人口的涌入和城市的扩张，变得越来越大。在快速扩张的过程中，市长为了方便管理，给交叉路口编号为 $0$ 到 $N-1$。这种编号系统具有以下特性：

• $0$ 号交叉路口是城市的中心，保证至少有两条道路与其相连。
• 交叉路口的编号是以 $0$ 号交叉路口为根的树的前序遍历顺序之一。
• 对于每个交叉路口，考虑与其相邻的（直接连接的）交叉路口中编号最小的一个。从这个交叉路口开始，按逆时针方向列出相邻交叉路口的编号，编号是递增的。

随着越来越多的人涌入 KOI 城市，交通拥堵问题变得越来越严重。市长决定通过建设外环道路来解决这个问题。将所有只有一条道路相连的交叉路口按编号递增的顺序排列，得到列表 $\{V[0], V[1], \ldots, V[K-1]\}$。市长决定在所有 $i$ $(0 \leq i \leq K-1)$ 的情况下，建设连接 $V[i]$ 和 $V[(i+1) \bmod K]$ 的双向道路。每条道路的权重为非负整数 $W[i]$。根据编号系统的特性，可以确保这些外环道路不会在端点之外的任何位置相交。

KOI 城市的邪恶犯罪团伙 Dlalswp 对市民造成了很大伤害。市长决定派遣情报人员来抓捕 Dlalswp 犯罪团伙。根据情报，Dlalswp 犯罪团伙将长度为奇数的简单环作为犯罪区域，并在这些环上进行犯罪活动。

为了抓捕臭名昭著的 Dlalswp 犯罪团伙，市长决定在所有长度为奇数的简单环上部署警察。每条道路上部署警察的成本等于该道路的权重。请计算市长实现目标所需的最小成本。

你需要实现以下函数：

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

• 该函数只会被调用一次。
• P：大小为 $N-1$ 的整数数组，表示建设外环道路前 KOI 城市的原始道路。对于每个 $0 \leq i \leq N-2$，存在一条连接 $P[i]$ 和 $i+1$ 的道路。
• C：大小为 $N-1$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-2)$，连接 $P[i]$ 和 $i+1$ 的道路的权重为 $C[i]$。
• W：大小为 $K$ 的整数数组。对于每个 $i$ $(0 \leq i \leq K-1)$，连接 $V[i]$ 和 $V[(i+1) \bmod K]$ 的双向道路的权重为 $W[i]$。
• 该函数返回在所有长度为奇数的简单环上部署警察的最小成本。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$P[i]\,C[i]$
• 第 $1+N$ 行：$W[0]\,W[1]\,\cdots\,W[K-1]$

输出格式

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

• 第 $1$ 行：函数 place_police 返回的值

4
0 9
0 8
0 0
9 9 9

9

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

1

提示

样例 1 解释

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

评测程序将调用如下函数：

place_police([0, 0, 0], [9, 8, 0], [9, 9, 9]);

KOI 城市中共有 $4$ 个奇数环，分别是 $\{0,1,2\},\{0,2,3\},\{0,3,1\},\{1,2,3\}$。如果市长在连接 $(0,3)$ 的权重为 $0$ 的道路和连接 $(1,2)$ 的权重为 $9$ 的道路上部署警察，那么所有奇数环上至少有一条道路上部署了警察。这个部署的成本是 $0+9=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=[1000000000000, \ldots, 1000000000000]$ 的情况。$W$ 的大小为 $6$，所有元素均为 $10^{12}$。

评测程序将调用如下函数：

place_police([0, 0, 2, 3, 3, 2, 0, 7, 7, 9], [9, 8, 0, 7, 1, 6, 0, 7, 1, 6], [1000000000000, 1000000000000, 1000000000000, 1000000000000, 1000000000000, 1000000000000]);

如果市长在连接 $(2,3)$ 的权重为 0 的道路、连接 $(0,7)$ 的权重为 0 的道路和连接 $(3,5)$ 的权重为 1 的道路上部署警察，那么所有奇数环上至少有一条道路上部署了警察。这个部署的成本是 $0+0+1=1$，这是实现目标的最小成本。

函数应返回 1。

数据范围

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

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

详细子任务附加限制及分值如下表所示。

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