P11342 [KTSC 2023 R1] 外环道路 2

**请勿使用 C++14 (GCC 9) 提交。** 请在程序开头加入如下代码： ```cpp #include long long place_police(std::vector P, std::vector C, std::vector W); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T2 「[외곽 순환 도로 2](https://assets.ioikorea.kr/ioitst/2023/1/ringroad2/ringroad2_statement.pdf)」** 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 犯罪团伙，市长决定在所有长度为奇数的简单环上部署警察。每条道路上部署警察的成本等于该道路的权重。请计算市长实现目标所需的最小成本。 你需要实现以下函数： ```cpp long long place_police(vector P, vector C, vector 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` 返回的值

### 样例 1 解释 考虑 $N=4, P=[0,0,0], C=[9,8,0], W=[9,9,9]$ 的情况。 评测程序将调用如下函数： ```cpp 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}$。 评测程序将调用如下函数： ```cpp 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$ | 无附加限制 |