Words on Tree
Contest: Educational Codeforces Round 125 (Rated for Div. 2)
Difficulty rating: 2600
Tags: 2-sat, dfs and similar, dsu, graphs, trees

You are given a tree consisting of $$$n$$$ vertices, and $$$q$$$ triples $$$(x_i, y_i, s_i)$$$, where $$$x_i$$$ and $$$y_i$$$ are integers from $$$1$$$ to $$$n$$$, and $$$s_i$$$ is a string with length equal to the number of vertices on the simple path from $$$x_i$$$ to $$$y_i$$$.

You want to write a lowercase Latin letter on each vertex in such a way that, for each of $$$q$$$ given triples, at least one of the following conditions holds:

- if you write out the letters on the vertices on the simple path from $$$x_i$$$ to $$$y_i$$$ in the order they appear on this path, you get the string $$$s_i$$$;
- if you write out the letters on the vertices on the simple path from $$$y_i$$$ to $$$x_i$$$ in the order they appear on this path, you get the string $$$s_i$$$.

Find any possible way to write a letter on each vertex to meet these constraints, or report that it is impossible.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 4 \cdot 10^5$$$; $$$1 \le q \le 4 \cdot 10^5$$$) — the number of vertices in the tree and the number of triples, respectively.

Then $$$n - 1$$$ lines follow; the $$$i$$$-th of them contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the endpoints of the $$$i$$$-th edge. These edges form a tree.

Then $$$q$$$ lines follow; the $$$j$$$-th of them contains two integers $$$x_j$$$ and $$$y_j$$$, and a string $$$s_j$$$ consisting of lowercase Latin letters. The length of $$$s_j$$$ is equal to the number of vertices on the simple path between $$$x_j$$$ and $$$y_j$$$.

Additional constraint on the input: $$$\sum \limits_{j=1}^{q} |s_j| \le 4 \cdot 10^5$$$.

Output format:
If there is no way to meet the conditions on all triples, print NO. Otherwise, print YES in the first line, and a string of $$$n$$$ lowercase Latin letters in the second line; the $$$i$$$-th character of the string should be the letter you write on the $$$i$$$-th vertex. If there are multiple answers, print any of them.

Constraints:
Time limit: 9.0 s
Memory limit: 1024.0 MB

Example input:
3 2
2 3
2 1
2 1 ab
2 3 bc

Example output:
YES
abc

Example input:
3 2
2 3
2 1
2 1 ab
2 3 cd

Example output:
NO

Editorial:
Let's design a naive solution first. For each of the given triples, we have two options: either write the string on the tree in the order from $$$x_i$$$ to $$$y_i$$$, or in reverse order. Some options conflict with each other. So, we can treat this problem as an instance of 2-SAT: create a variable for each of the given strings, which is true if the string is not reversed, and false if it is reversed; find all conflicting pairs of options and then run the usual algorithm for solving 2-SAT.
Unfortunately, the number of conflicting pairs can be up to $$$O(n^2)$$$, so we need to improve this solution. Let's introduce a variable for each vertex of the tree which will define the character we write on it. At first, it looks like we can't use these variables in 2-SAT, since the number of possible characters is $$$26$$$, not $$$2$$$. But if a vertex is covered by at least one path in a triple, then there are only two possible characters we can write in this vertex: either the character which will land on this position if we write the string from $$$x_i$$$ to $$$y_i$$$, or the character on the opposite position in the string $$$s_i$$$. And, obviously, if a vertex is not covered by any triple, we can write any character on it.
Okay, now for each vertex $$$i$$$, we have two options for a character: $$$c_{i,1}$$$ and $$$c_{i,2}$$$. Let the variable $$$p_i$$$ be true if we write $$$c_{i,1}$$$ on vertex $$$i$$$, and false if we write $$$c_{i,2}$$$. Also, for each triple $$$j$$$, let's introduce a variable $$$w_j$$$ which is true if the string $$$s_j$$$ is written from $$$x_j$$$ to $$$y_j$$$, and false if it is written in reversed order. If the vertex $$$i$$$ is the $$$k$$$-th one on the path from $$$x_j$$$ to $$$y_j$$$, then we should add the following constraints in our 2-SAT:
• if $$$s_{j,k} \ne c_{i,1}$$$, we need a constraint "NOT $$$p_i$$$ OR NOT $$$w_j$$$";
• if $$$s_{j,k} \ne c_{i,2}$$$, we need a constraint "$$$p_i$$$ OR NOT $$$w_j$$$";
• if $$$s_{j,|s_j|-k+1} \ne c_{i,1}$$$, we need a constraint "NOT $$$p_i$$$ OR $$$w_j$$$";
• if $$$s_{j,|s_j|-k+1} \ne c_{i,2}$$$, we need a constraint "$$$p_i$$$ OR $$$w_j$$$".
Thus, we add at most $$$16 \cdot 10^5$$$ constraints in our 2-SAT. The only thing we haven't discussed is how to actually restore each path from $$$x_j$$$ to $$$y_j$$$; this can be done either with any fast algorithm that finds LCA, or by searching for LCA "naively" by ascending from one of those vertices until we arrive at the ancestor of another vertex; this approach will visit at most $$$\sum \limits_{j=1}^{q} |s_j|$$$ vertices.
Overall, this solution runs in $$$O(n + q + \sum \limits_{j=1}^{q} |s_j|)$$$.