P11634 [CTS2025] 仙人掌染色（暂无数据）

IOI 2025 中国国家队选拔 d2t1。

定义一个**无自环、无重边的无向连通图**是**仙人掌图**，当且仅当其**任意一条边至多属于一个简单环**，其中简单环指不经过重复结点的环。 给定平面上的 $n$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。给定 $m$ 条边，第 $i$ 条边连接结点 $u_i, v_i$。**保证由这 $n$ 个点与 $m$ 条边构成的无向图为仙人掌图**。 初始时，所有的 $m$ 条边都是白色的。你可以选择若干条边，并将其染成黑色，其中将第 $i$ 条边染成黑色的代价为 $w_i$。对于每对有公共结点的异色边，设从白色边开始沿公共结点**逆时针**转 $x$ 条边可以到达黑色边，那么可以获得 $p\times x$ 的能量。特别地，对于两条共线且方向相同的边（即另一结点关于公共结点的极角相同的边），规定先到达编号较小的边，也即，编号较小的边的极角更小。 求染色后可以获得的能量总和减去染色代价总和的最大值。

输入的第一行三个正整数 $n, m, p$，分别表示结点个数、边数、以及获得能量的系数。 接下来 $m$ 行，第 $i$ 行三个整数 $u_i, v_i, w_i$，表示第 $i$ 条边的结点与代价。 接下来 $n$ 行，第 $i$ 行两个整数 $x_i, y_i$，表示第 $i$ 个点的坐标。

输出一行一个整数，表示染色后可以获得的能量总和减去染色代价总和的最大值。

### 样例解释 #### 样例 $1$ 解释 如下图所示，黑色实线表示被染成黑色的边，灰色点线表示仍为白色的边。 花费 $2$ 的代价将 $(3, 4)$ 染为黑色后，从 $(1, 4)$ 沿结点 $4$ 逆时针转 $1$ 条边可以到达 $(3, 4)$，获得 $10 \times 1 = 10$ 能量；从 $(2, 3)$ 沿结点 $3$ 逆时针转 $1$ 条边可以到达 $(3, 4)$（注意：根据题目描述中的规定，会先到达 $(3, 4)$ 后到达 $(3, 5)$），获得 $10 \times 1 = 10$ 能量；从 $(3, 5)$ 沿结点 $3$ 逆时针转 $2$ 条边可以到达 $(3, 4)$，获得 $10 \times 2 = 20$ 能量。因此染色后可以获得的能量总和为 $10 + 10 + 20 = 40$，代价总和为 $2$，所求的最大值为 $40 − 2 = 38$。 可以证明，不存在答案更大的染色方案。 ### 数据范围 对于所有测试数据，保证 - $2 \le n, m \le 2 \times 10^5$，$1 \le p \le 1000$， - $\forall 1 \le i \le m, 1 \le u_i, v_i \le n, 0 \le w_i \le 10^4$， - $\forall 1 \le i \le n, 0 \le x_i, y_i \le 10^7$， - 给定的图是仙人掌图； - 任意两个点坐标不重合。 | 子任务编号 | 分值 | $n,m\le$ | 特殊性质 | | :--: | :--: | :--: | :--: | | $1$ | $7$ | $20$ | AB | | $2$ | $9$ | $20$ | 无 | | $3$ | $3$ | $8,000$ | AB | | $4$ | $9$ | $8,000$ | A | | $5$ | $30$ | $8,000$ | 无 | | $6$ | $11$ | $2\times 10^5$ | A | | $7$ | $1$ | $2\times 10^5$ | C | | $8$ | $12$ | $2\times 10^5$ | D | | $9$ | $18$ | $2\times 10^5$ | 无 | - 特殊性质 A：保证 $m = n − 1$，也即给定的图是一棵树。 - 特殊性质 B：保证给定的图上任意一对没有公共结点的边在平面上不相交，也即给定的图是平面嵌入。 - 特殊性质 C：保证 $\forall 1 \le i \le m, w_i = 0$。 - 特殊性质 D：保证 $\forall 1 \le i \le m, w_i = 1$，$p = 1$。