CF1904F Beautiful Tree

Lunchbox 有一棵大小为 $n$ 的树，根节点为 $1$。每个节点都需要被赋予一个值。Lunchbox 认为这棵树是美丽的，当且仅当每个节点的值互不相同，且这些值恰好为 $1$ 到 $n$ 的一个排列。此外，一棵美丽的树还必须满足 $m$ 个关于以下两种类型的要求： - “1 a b c” —— 在节点 $a$ 和 $b$ 之间的路径上，值最小的节点必须是 $c$。 - “2 a b c” —— 在节点 $a$ 和 $b$ 之间的路径上，值最大的节点必须是 $c$。 现在，你需要为每个节点分配一个值，使得最终的树是美丽的。如果无法做到，请输出 $-1$。

第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$）。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n, u \ne v$），表示节点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。 接下来的 $m$ 行，每行包含四个整数 $t$、$a$、$b$ 和 $c$（$t \in \{1,2\}$，$1 \le a, b, c \le n$）。保证节点 $c$ 在节点 $a$ 和 $b$ 之间的路径上。

如果无法分配出满足条件的值，使得树是美丽的，输出 $-1$。否则，输出 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的值。

由 ChatGPT 4.1 翻译