Words on Tree (Codeforces 1657F)
Tags: Others, 2-sat

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: 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: 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.


Sample Inputs:
3 2
2 3
2 1
2 1 ab
2 3 bc

3 2
2 3
2 1
2 1 ab
2 3 cd

10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 ab
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba

10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 aa
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba

Sample Outputs:
YES
abc

NO

YES
baaaaaaaaa

NO

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for j in G[i]:
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (dist, parent)
e = []

def add_edge(u, v, tu, tv):
    e.append(u if not tu else u + n)
    e.append(v + n if not tv else v)
    e.append(v if not tv else v + n)
    e.append(u + n if not tu else u)
    return

def make_graph(n, e):
    m = len(e) // 2
    (s1, s2) = ([0] * (n + 3), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        s1[e[i] + 2] += 1
        s2[e[i + 1] + 2] += 1
    for i in range(3, n + 3):
        s1[i] += s1[i - 1]
        s2[i] += s2[i - 1]
    (G, R) = ([0] * m, [0] * m)
    for i in range(2 * m):
        j = e[i] + 1
        if not i % 2:
            G[s1[j]] = e[i ^ 1]
            s1[j] += 1
        else:
            R[s2[j]] = e[i ^ 1]
            s2[j] += 1
    return (G, s1, R, s2)

def scc(n, G, s1, R, s2):
    now = list(s1)
    st = []
    u = [0] * (n + 1)
    c = 1
    for i in range(1, n + 1):
        if u[i]:
            continue
        (st, u[i]) = ([i], -1)
        while st:
            j = st[-1]
            while now[j] < s1[j + 1] and u[G[now[j]]]:
                now[j] += 1
            if now[j] == s1[j + 1]:
                u[st.pop()] = c
                c += 1
            else:
                st.append(G[now[j]])
                u[st[-1]] = -1
    v = [0] * n
    for i in range(1, n + 1):
        v[u[i] - 1] = i
    (c, z) = ([0] * (n + 1), 1)
    for i in v[::-1]:
        if c[i]:
            continue
        (q, l, c[i]) = ([i], 0, z)
        while len(q) ^ l:
            j = q[l]
            for w in range(s2[j], s2[j + 1]):
                k = R[w]
                if not c[k]:
                    q.append(k)
                    c[k] = z
            l += 1
        z += 1
    return c

def two_sat():
    (G, s1, R, s2) = make_graph(2 * n, e)
    c = scc(2 * n, G, s1, R, s2)
    (ok, z) = (1, [0] * (n + 1))
    for i in range(1, n + 1):
        if c[i] == c[i + n]:
            ok = 0
        elif c[i] < c[i + n]:
            z[i] = 1
    return (ok, z)
(n, q) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
inf = pow(10, 9) + 1
(dist, parent) = bfs(1)
pow2 = [1]
for _ in range(26):
    pow2.append(2 * pow2[-1])
b = [pow2[26] - 1] * (n + 1)
(x0, s0) = ([], [])
for _ in range(q):
    (u, v, s) = input().rstrip().decode().split()
    (u, v, s) = (int(u), int(v), [ord(i) - 97 for i in s])
    t = s[::-1]
    if dist[u] > dist[v]:
        (u, v) = (v, u)
    (x, y) = ([u], [v])
    while dist[u] ^ dist[y[-1]]:
        y.append(parent[y[-1]])
    while x[-1] ^ y[-1]:
        x.append(parent[x[-1]])
        y.append(parent[y[-1]])
    x += y[:-1][::-1]
    for (i, j, k) in zip(x, s, t):
        b[i] &= pow2[j] | pow2[k]
    x0.append(x)
    s0.append(s)
if not min(b):
    ans = 'NO'
    print(ans)
    exit()
(u, v) = ([0] * (n + 1), [0] * (n + 1))
for i in range(1, n + 1):
    if b[i] == pow2[26] - 1:
        continue
    u[i] = b[i].bit_length() - 1
    b[i] ^= pow2[u[i]]
    v[i] = b[i].bit_length() - 1 if b[i] else u[i]
for (x, s) in zip(x0, s0):
    t = s[::-1]
    i = 0
    for j in range(len(s)):
        if s[j] ^ t[j]:
            i = j
            break
    for l in range(len(x)):
        (j, k) = (x[i], x[l])
        if j < k:
            se = set([(s[i], s[l]), (t[i], t[l])])
        else:
            (j, k) = (k, j)
            se = set([(s[l], s[i]), (t[l], t[i])])
        if not (u[j], u[k]) in se:
            add_edge(j, k, 0, 0)
        if not (u[j], v[k]) in se:
            add_edge(j, k, 0, 1)
        if not (v[j], u[k]) in se:
            add_edge(j, k, 1, 0)
        if not (v[j], v[k]) in se:
            add_edge(j, k, 1, 1)
(ok, z) = two_sat()
ans = 'YES' if ok else 'NO'
print(ans)
if not ok:
    exit()
ans = [chr(i + 97) if not k else chr(j + 97) for (i, j, k) in zip(u, v, z)][1:]
sys.stdout.write(''.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for j in G[i]:
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (dist, parent)
e = []

def add_edge(u, v, tu, tv):
    e.append(u if not tu else u + n)
    e.append(v + n if not tv else v)
    e.append(v if not tv else v + n)
    e.append(u + n if not tu else u)
    return

def make_graph(n, e):
    m = len(e) // 2
    (s1, s2) = ([0] * (n + 3), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        s1[e[i] + 2] += 1
        s2[e[i + 1] + 2] += 1
    for i in range(3, n + 3):
        s1[i] += s1[i - 1]
        s2[i] += s2[i - 1]
    (G, R) = ([0] * m, [0] * m)
    for i in range(2 * m):
        j = e[i] + 1
        if not i % 2:
            G[s1[j]] = e[i ^ 1]
            s1[j] += 1
        else:
            R[s2[j]] = e[i ^ 1]
            s2[j] += 1
    return (G, s1, R, s2)

def scc(n, G, s1, R, s2):
    now = list(s1)
    st = []
    u = [0] * (n + 1)
    c = 1
    for i in range(1, n + 1):
        if u[i]:
            continue
        (st, u[i]) = ([i], -1)
        while st:
            j = st[-1]
            while now[j] < s1[j + 1] and u[G[now[j]]]:
                now[j] += 1
            if now[j] == s1[j + 1]:
                u[st.pop()] = c
                c += 1
            else:
                st.append(G[now[j]])
                u[st[-1]] = -1
    v = [0] * n
    for i in range(1, n + 1):
        v[u[i] - 1] = i
    (c, z) = ([0] * (n + 1), 1)
    for i in v[::-1]:
        if c[i]:
            continue
        (q, l, c[i]) = ([i], 0, z)
        while len(q) ^ l:
            j = q[l]
            for w in range(s2[j], s2[j + 1]):
                k = R[w]
                if not c[k]:
                    q.append(k)
                    c[k] = z
            l += 1
        z += 1
    return c

def two_sat():
    (G, s1, R, s2) = make_graph(2 * n, e)
    c = scc(2 * n, G, s1, R, s2)
    (ok, z) = (1, [0] * (n + 1))
    for i in range(1, n + 1):
        if c[i] == c[i + n]:
            ok = 0
        elif c[i] < c[i + n]:
            z[i] = 1
    return (ok, z)
(n, q) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
inf = pow(10, 9) + 1
(dist, parent) = bfs(1)
pow2 = [1]
for _ in range(26):
    pow2.append(2 * pow2[-1])
b = [pow2[26] - 1] * (n + 1)
(x0, s0) = ([], [])
for _ in range(q):
    (u, v, s) = input().rstrip().decode().split()
    (u, v, s) = (int(u), int(v), [ord(i) - 97 for i in s])
    t = s[::-1]
    if dist[u] > dist[v]:
        (u, v) = (v, u)
    (x, y) = ([u], [v])
    while dist[u] ^ dist[y[-1]]:
        y.append(parent[y[-1]])
    while x[-1] ^ y[-1]:
        x.append(parent[x[-1]])
        y.append(parent[y[-1]])
    x += y[:-1][::-1]
    for (i, j, k) in zip(x, s, t):
        b[i] &= pow2[j] | pow2[k]
    x0.append(x)
    s0.append(s)
if not min(b):
    ans = 'NO'
    print(ans)
    exit()
(u, v) = ([0] * (n + 1), [0] * (n + 1))
for i in range(1, n + 1):
    if b[i] == pow2[26] - 1:
        continue
    u[i] = b[i].bit_length() - 1
    b[i] ^= pow2[u[i]]
    v[i] = b[i].bit_length() - 1 if b[i] else u[i]
for (x, s) in zip(x0, s0):
    t = s[::-1]
    for l in [1, 2]:
        for i in range(len(x) - l):
            (j, k) = (x[i], x[i + l])
            if j < k:
                se = set([(s[i], s[i + l]), (t[i], t[i + l])])
            else:
                (j, k) = (k, j)
                se = set([(s[i + l], s[i]), (t[i + l], t[i])])
            if not (u[j], u[k]) in se:
                add_edge(j, k, 0, 0)
            if not (u[j], v[k]) in se:
                add_edge(j, k, 0, 1)
            if not (v[j], u[k]) in se:
                add_edge(j, k, 1, 0)
            if not (v[j], v[k]) in se:
                add_edge(j, k, 1, 1)
    i = -1
    for j in range(len(s)):
        if s[j] ^ t[j]:
            i = j
            break
    if i == -1:
        continue
    for l in range(len(x)):
        (j, k) = (x[i], x[l])
        if j < k:
            se = set([(s[i], s[l]), (t[i], t[l])])
        else:
            (j, k) = (k, j)
            se = set([(s[l], s[i]), (t[l], t[i])])
        if not (u[j], u[k]) in se:
            add_edge(j, k, 0, 0)
        if not (u[j], v[k]) in se:
            add_edge(j, k, 0, 1)
        if not (v[j], u[k]) in se:
            add_edge(j, k, 1, 0)
        if not (v[j], v[k]) in se:
            add_edge(j, k, 1, 1)
(ok, z) = two_sat()
ans = 'YES' if ok else 'NO'
print(ans)
if not ok:
    exit()
ans = [chr(i + 97) if not k else chr(j + 97) for (i, j, k) in zip(u, v, z)][1:]
sys.stdout.write(''.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for j in G[i]:
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (dist, parent)
e = []

def add_edge(u, v, tu, tv):
    e.append(u if not tu else u + n)
    e.append(v + n if not tv else v)
    e.append(v if not tv else v + n)
    e.append(u + n if not tu else u)
    return

def make_graph(n, e):
    m = len(e) // 2
    (s1, s2) = ([0] * (n + 3), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        s1[e[i] + 2] += 1
        s2[e[i + 1] + 2] += 1
    for i in range(3, n + 3):
        s1[i] += s1[i - 1]
        s2[i] += s2[i - 1]
    (G, R) = ([0] * m, [0] * m)
    for i in range(2 * m):
        j = e[i] + 1
        if not i % 2:
            G[s1[j]] = e[i ^ 1]
            s1[j] += 1
        else:
            R[s2[j]] = e[i ^ 1]
            s2[j] += 1
    return (G, s1, R, s2)

def scc(n, G, s1, R, s2):
    now = list(s1)
    st = []
    u = [0] * (n + 1)
    c = 1
    for i in range(1, n + 1):
        if u[i]:
            continue
        (st, u[i]) = ([i], -1)
        while st:
            j = st[-1]
            while now[j] < s1[j + 1] and u[G[now[j]]]:
                now[j] += 1
            if now[j] == s1[j + 1]:
                u[st.pop()] = c
                c += 1
            else:
                st.append(G[now[j]])
                u[st[-1]] = -1
    v = [0] * n
    for i in range(1, n + 1):
        v[u[i] - 1] = i
    (c, z) = ([0] * (n + 1), 1)
    for i in v[::-1]:
        if c[i]:
            continue
        (q, l, c[i]) = ([i], 0, z)
        while len(q) ^ l:
            j = q[l]
            for w in range(s2[j], s2[j + 1]):
                k = R[w]
                if not c[k]:
                    q.append(k)
                    c[k] = z
            l += 1
        z += 1
    return c

def two_sat():
    (G, s1, R, s2) = make_graph(2 * n, e)
    c = scc(2 * n, G, s1, R, s2)
    (ok, z) = (1, [0] * (n + 1))
    for i in range(1, n + 1):
        if c[i] == c[i + n]:
            ok = 0
        elif c[i] < c[i + n]:
            z[i] = 1
    return (ok, z)
(n, q) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
inf = pow(10, 9) + 1
(dist, parent) = bfs(1)
pow2 = [1]
for _ in range(26):
    pow2.append(2 * pow2[-1])
b = [pow2[26] - 1] * (n + 1)
(x0, s0) = ([], [])
for _ in range(q):
    (u, v, s) = input().rstrip().decode().split()
    (u, v, s) = (int(u), int(v), [ord(i) - 97 for i in s])
    t = s[::-1]
    if dist[u] > dist[v]:
        (u, v) = (v, u)
    (x, y) = ([u], [v])
    while dist[u] ^ dist[y[-1]]:
        y.append(parent[y[-1]])
    while x[-1] ^ y[-1]:
        x.append(parent[x[-1]])
        y.append(parent[y[-1]])
    x += y[:-1][::-1]
    for (i, j, k) in zip(x, s, t):
        b[i] &= pow2[j] | pow2[k]
    x0.append(x)
    s0.append(s)
if not min(b):
    ans = 'NO'
    print(ans)
    exit()
(u, v) = ([0] * (n + 1), [0] * (n + 1))
for i in range(1, n + 1):
    if b[i] == pow2[26] - 1:
        continue
    u[i] = b[i].bit_length() - 1
    b[i] ^= pow2[u[i]]
    v[i] = b[i].bit_length() - 1 if b[i] else u[i]
for (x, s) in zip(x0, s0):
    t = s[::-1]
    i = 0
    for j in range(len(s)):
        if s[j] ^ t[j]:
            i = j
            break
    for l in range(len(x)):
        (j, k) = (x[i], x[l])
        if j < k:
            se = set([(s[i], s[l]), (t[i], t[l])])
        else:
            (j, k) = (k, j)
            se = set([(s[l], s[i]), (t[l], t[i])])
        if not (u[j], u[k]) in se:
            add_edge(j, k, 0, 0)
        if not (u[j], v[k]) in se:
            add_edge(j, k, 0, 1)
        if not (v[j], u[k]) in se:
            add_edge(j, k, 1, 0)
        if not (v[j], v[k]) in se:
            add_edge(j, k, 1, 1)
(ok, z) = two_sat()
ans = 'YES' if ok else 'NO'
print(ans)
if not ok:
    exit()
ans = [chr(i + 97) if not k else chr(j + 97) for (i, j, k) in zip(u, v, z)][1:]
sys.stdout.write(''.join(ans))