CF1657F Words on Tree

给定一棵包含 $n$ 个顶点的树，以及 $q$ 个三元组 $(x_i, y_i, s_i)$，其中 $x_i$ 和 $y_i$ 是 $1$ 到 $n$ 之间的整数，$s_i$ 是一个字符串，其长度等于从 $x_i$ 到 $y_i$ 的简单路径上的顶点数。 你需要在每个顶点上写一个小写拉丁字母，使得对于每个给定的三元组，至少满足以下两个条件之一： - 如果你按照从 $x_i$ 到 $y_i$ 的路径顺序写出路径上顶点的字母，得到的字符串是 $s_i$； - 如果你按照从 $y_i$ 到 $x_i$ 的路径顺序写出路径上顶点的字母，得到的字符串是 $s_i$。 请找出一种可能的方式，在每个顶点上写一个字母，使得所有三元组的约束都被满足。如果不存在这样的方案，请输出不可能。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 4 \cdot 10^5$，$1 \le q \le 4 \cdot 10^5$），分别表示树的顶点数和三元组的数量。 接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条边的两个端点。这些边构成一棵树。 接下来 $q$ 行，每行包含两个整数 $x_j$ 和 $y_j$，以及一个由小写拉丁字母组成的字符串 $s_j$。$s_j$ 的长度等于从 $x_j$ 到 $y_j$ 的简单路径上的顶点数。 输入还满足额外限制：$\sum\limits_{j=1}^{q} |s_j| \le 4 \cdot 10^5$。

如果不存在满足所有三元组条件的方案，输出 NO。否则，第一行输出 YES，第二行输出一个长度为 $n$ 的小写字母字符串，第 $i$ 个字符表示你在第 $i$ 个顶点上写的字母。如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译