AT_ahc041_a [AHC041A] Christmas Tree Cutting

AtCoderオフィスでは、一足遅いクリスマスパーティーの準備が進められている。高橋社長は、クリスマスツリーに使う根付き木を切りに行くことにした。 根付き木の各頂点は **美しさ** を持ち、高いところに美しい頂点が存在するとパーティー会場の **見栄え** が良くなる。ただし、根付き木が高すぎるとAtCoderオフィスの天井にぶつかってしまうため、パーティー会場に持ち込むことのできる根付き木の高さには制限がかけられている。 与えられたグラフから根付き木をいくつか切り出して、できるだけパーティー会場の **見栄え** を良くして欲しい。

给定一个包含 $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}$ [查看示例](https://img.atcoder.jp/ahc041/m0Bwp9WL.html?lang=ja&seed=0&output=sample) 你可以多次输出解答。如果输出了多组解答，则只会以最后一组为评分依据。使用网页版可视化工具可以比较多组解答的效果。

## 故事背景 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$，计算其[德劳内三角剖分](https://zh.wikipedia.org/wiki/%E5%BE%B7%E5%8A%B3%E5%86%85%E5%9B%BE)，将三角剖分的边集作为 $E$，得到 $G=(V, E)$。 ### 美丽值 $A$ 的生成 顶点 $v$ 的美丽值 $A_v = \mathrm{rand}(1, 100)$。 ## 工具（输入生成器、本地测试器、可视化工具） - [网页版](https://img.atcoder.jp/ahc041/m0Bwp9WL.html?lang=ja)：功能更强大，支持动画显示。 - [本地版](https://img.atcoder.jp/ahc041/m0Bwp9WL.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制](https://img.atcoder.jp/ahc041/m0Bwp9WL_windows.zip)：不想配置 Rust 环境可直接使用。 比赛期间，禁止分享可视化结果、讨论解法或思路。请注意遵守规则。 由 ChatGPT 4.1 翻译