AT_ahc041_a.[AHC041A] Christmas Tree Cutting

给定一个包含 $N$ 个顶点和 $M$ 条边的连通无向平面图 $G$。顶点编号为 $0$ 到 $N-1$，边编号为 $0$ 到 $M-1$。顶点 $v$ 的坐标为 $(x_v, y_v)$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。每个顶点都被赋予了一个正整数的“美丽值”，顶点 $v$ 的美丽值为 $A_v$。

定义有根树 $T$ 的“观赏值”如下。$T$ 中顶点 $v$ 的“高度” $h_v$，为从根到 $v$ 的路径上包含的边的数量。此时，有根树 $T$ 的“观赏值” $a(T)$ 定义为 $a(T):=\sum_{v\in T} (h_v+1)A_v$。

请从给定的图 $G$ 中构造若干满足以下条件的有根树集合，使得“观赏值”的总和尽可能大。

• 每棵有根树 $T$ 所包含的边均属于 $G$。
• $G$ 的每个顶点恰好属于一棵有根树。
• 每棵有根树中所有顶点的高度均不超过 $H$。

输入通过标准输入按以下格式给出。

$N$ $M$ $H$
$A_0$ $A_1$ $\cdots$ $A_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$x_0$ $y_0$
$\vdots$
$x_{N-1}$ $y_{N-1}$

输入满足以下约束条件：

• $N=1000$
• $1000 \leq M \leq 3000$
• $H=10$
• $1 \leq A_v \leq 100$
• $0 \leq u_i < v_i \leq N-1$
• $0 \leq x_v, y_v \leq 1000$
• 所有 $(x_v, y_v)$ 坐标均互不相同。
• 所有输入均为整数。
• 给定的图是连通的平面图。将顶点 $v$ 放置在坐标 $(x_v, y_v)$，每条边画为连接两端点的线段时，任意两条边除了端点外没有公共点。

对于你构造的有根树集合，输出每个顶点 $v$ 的父节点编号 $p_v$（若 $v$ 是根，则 $p_v=-1$），格式如下：

$p_0$ $p_1$ $\cdots$ $p_{N-1}$

查看示例

你可以多次输出解答。如果输出了多组解答，则只会以最后一组为评分依据。使用网页版可视化工具可以比较多组解答的效果。

故事背景

AtCoder 办公室正在准备一个迟到的圣诞派对。高桥社长决定去砍一些用于圣诞树的有根树。

每个有根树的顶点都有“美丽值”，如果高处有美丽的顶点，派对会场的“观赏值”就会更高。不过，如果有根树太高，就会碰到 AtCoder 办公室的天花板，因此能带进会场的有根树高度有限制。

请从给定的图中切割出若干有根树，使会场的“观赏值”尽可能高。

评分

设你输出的有根树集合为 $F$，则得分为 $1+\sum_{T\in F} a(T)$。

共有 150 个测试用例，所有测试用例得分之和为你的提交得分。如果有任意一个测试用例输出非法或超时，则整份提交判为 WA 或 TLE。比赛期间以你获得的最高分计入最终排名，赛后不再进行系统测试。若多名参赛者得分相同，则排名并列。

输入生成方法

用 $\mathrm{rand}(L, U)$ 表示在 $L$ 到 $U$ 之间等概率随机生成的整数。

图 $G$ 的生成

以 $(500,500)$ 为圆心、半径为 $500$ 的圆内的格点中，随机依次选取 $N$ 个点作为 $(x_0, y_0), \cdots, (x_{N-1}, y_{N-1})$。若与已选点的欧几里得距离不超过 $15$，则重新选择。

对得到的顶点集合 $V$，计算其德劳内三角剖分，将三角剖分的边集作为 $E$，得到 $G=(V, E)$。

美丽值 $A$ 的生成

顶点 $v$ 的美丽值 $A_v = \mathrm{rand}(1, 100)$。

工具（输入生成器、本地测试器、可视化工具）

• 网页版：功能更强大，支持动画显示。
• 本地版：需安装 Rust 语言 编译环境。
• Windows 版编译好的二进制：不想配置 Rust 环境可直接使用。

比赛期间，禁止分享可视化结果、讨论解法或思路。请注意遵守规则。

由 ChatGPT 4.1 翻译