CF1296F Berland Beauty

在 Berland 有 $n$ 个火车站。这些火车站通过 $n-1$ 条铁路线段相互连接。整个铁路网络是连通的，也就是说可以表示为一棵无向树。 你有这张网络的地图，因此你知道每条铁路线段连接的是哪两个车站。 每条铁路线段都有一个整数值，表示风景的美丽度。但这些值没有标在地图上，你也不知道它们。所有这些值都在 $1$ 到 $10^6$ 之间（包含 $1$ 和 $10^6$）。 你询问了 $m$ 位乘客一些问题：第 $j$ 位乘客告诉了你三个值： - 他的出发站 $a_j$； - 他的到达站 $b_j$； - 从 $a_j$ 到 $b_j$ 的路径上所有铁路线段中的最小风景美丽度（列车沿着 $a_j$ 到 $b_j$ 的最短路径行驶）。 你计划更新地图，并为每条铁路线段设置一个风景美丽度 $f_i$。这些值需要与乘客的回答一致。 请输出任意一组满足条件的 $f_1, f_2, \dots, f_{n-1}$，使得所有乘客的回答都与这些值一致；如果不存在这样的方案，则输出 $-1$。

第一行包含一个整数 $n$（$2 \le n \le 5000$），表示 Berland 的火车站数量。 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n, x_i \ne y_i$），表示第 $i$ 条铁路线段连接的两个车站编号。所有铁路线段都是双向的。任意两个车站之间都可以通过铁路到达。 接下来一行包含一个整数 $m$（$1 \le m \le 5000$），表示被询问的乘客数量。接下来的 $m$ 行，每行包含三个整数 $a_j$、$b_j$ 和 $g_j$（$1 \le a_j, b_j \le n$；$a_j \ne b_j$；$1 \le g_j \le 10^6$），分别表示出发站、到达站和这条路径上所有铁路线段的最小风景美丽度。

如果不存在满足条件的方案，则输出一个整数 $-1$。 否则，输出 $n-1$ 个整数 $f_1, f_2, \dots, f_{n-1}$（$1 \le f_i \le 10^6$），其中 $f_i$ 表示第 $i$ 条铁路线段的风景美丽度。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译