欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

题目大意

https://codeforces.com/contest/1657/problem/F
$给定一棵n个结点（每个结点上标记有一个小写字母）的数和q个三元组(x_i,y_i,s_i)。$

$$\begin{gathered} x_i,y_i是树上的2个结点编号，s_i是一个小写字母组成的字符串， \\ 长度是从树上x_i到y_i的路径经过结点的个数 \end{gathered}$$

$如果把从x_i到y_i（可y_i到x_i）路径的字母顺序排列可得到s_i则s_i是合法的。$
问每个结点的字母要怎么选择才能满足所有si.

分析&思路

对于有被s覆盖的点来说，选择就只有2个，要么顺序摆放，要么倒序摆放，对于没有被s覆盖的点，可以直接取a。基本思路就是用2sat来解决。

分析一下2sat建立边的过程。
对于结点i来说有2个选择ci1, ci2，设置变量pi, 如果pi=false则选择ci1, 否则选择ci2。这样还不够，因为每个结点之间还要通过s来联系，所以再加入一个变量wj, 如果wj=false代表sj是从xj到yj顺序放，否则是倒序放。

首先根据路径查找出sj对应到树上的结点。然后标记这些节点的可选字母。
假设对于一个sj来说, 结点数组为A，第k个结点可以选择C1， C2.

然后是根据条件进行设置。
$假设第i个结点对应s_j路径上的第k个顺序结点$
$1如果s_{j,k}!=c_{i,1},设置条件p_i=true||w_j=true$

$2如果s_{j,k}!=c_{i,2},设置条件p_i=false||w_j=true$

$3如果s_{j,|s_j|-k+1}!=c_{i,1},设置条件p_i=true||w_j=false$

$3如果s_{j,|s_j|-k+1}!=c_{i,2},设置条件p_i=false||w_j=false$

AC代码

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <stack>
#include <vector>
#include <algorithm>
#include <assert.h>

using namespace std;


const int N = 4e6 +10;
const int E = 4e6+10;
// 边属性
class Edge {
public:
    int toVertex;
    int nextEdge;
};

// 点属性
class Node {
public:
    int head;
};

class Graph {
public:
    Edge edges[E];
    Node nodes[N];
    int usedEdge=0;
    Graph() {
        usedEdge = 0;
    }

    void initEdge(int n) {
        for(int i=0;i<=n;++i) {
            nodes[i].head=-1;
        }
        usedEdge = 0;
    }

    void addEdge(int a, int b) {
        if(a==b) return;
        edges[usedEdge].nextEdge = nodes[a].head;
        nodes[a].head = usedEdge;
        edges[usedEdge].toVertex = b;

        usedEdge++;

        // cout<<"add edge: "<<a<<" "<<b<<endl;
    }
};

Graph og, tree;

int father[N], high[N];

void initHigh(int u) {
    for(int i=tree.nodes[u].head;i>=0; i=tree.edges[i].nextEdge) {
        int v = tree.edges[i].toVertex;
        if(v==father[u])continue;
        father[v]=u;
        high[v]=high[u]+1;
        initHigh(v);
    }
}

vector<int> getPath(int u, int v) {
    vector<int> l, r;

    while(u!=v) {
        if(high[u]>high[v]) {
            l.push_back(u);
            u=father[u];
        }else {
            r.push_back(v);
            v=father[v];
        }
    }

    l.push_back(u);
    l.insert(l.end(), r.rbegin(), r.rend());

    return l;
}


int dfn[N], low[N];
stack<int> st;
int deep, sum;
int color[N];

void initTarjan() {
    deep = 0;
    sum=0;
    memset(dfn, 0,sizeof(dfn));
    memset(low, 0,sizeof(low));
    memset(color, 0,sizeof(color));
}

void tarjan(int u) {
    dfn[u] = ++deep;
    low[u] = deep;
    st.push(u);

    for(int i=og.nodes[u].head;i>=0;i = og.edges[i].nextEdge) {
        int v = og.edges[i].toVertex;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u]==low[u]) {
        color[u] = ++sum;
        while(st.top()!=u) {
            int v = st.top();
            st.pop();
            color[v]=sum;
        }
        st.pop();
    }
}

pair<char, char> opts[N];

char cstr[N];

void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;++i) {
        opts[i] = {'a','a'};
    }
    int nm =  (n*2+m*2);

    tree.initEdge(n+10);
    for(int i=1;i<n;++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        tree.addEdge(a, b);
        tree.addEdge( b,a);
    }
    father[1]=-1;
    high[1]=1;

    initHigh(1);
    vector<vector<int>> paths(m);
    vector<string> strs(m);
    og.initEdge(nm+10);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d%s", &u, &v, cstr);
        strs[i]=cstr;
        // cout<<u<<v<<strs[i]<<endl;
        // continue;
        paths[i] = getPath(u, v);
        /*
        for(auto x:paths[i]) {
            printf("%d ", x);
        }
        puts("");
         */
        int sl = strlen(cstr);
        assert(int(paths[i].size()) == sl);
        for(int j=0;j<sl;++j) {
            opts[paths[i][j]] = {cstr[j], cstr[sl-1-j]};
        }
    }

    for(int i=0;i<m;++i) {
        int sl = strs[i].size();
        for(int j=0;j<sl;++j) {
            int v = paths[i][j];
            int c = strs[i][j], rc = strs[i][sl-1-j];
            int d = opts[v].first, rd = opts[v].second;
            if(c!=d) {
                og.addEdge(v+n, 2*n+1+i);
                og.addEdge(2*n+1+i+m, v);
            }

            if(c!=rd) {
                og.addEdge(v, 2*n+1+i);
                og.addEdge(2*n+1+i+m, v+n);
            }

            if(rc!=d) {
                og.addEdge(v+n, 2*n+1+i+m);
                og.addEdge(2*n+1+i, v);
            }

            if(rc!=rd ) {
                og.addEdge(v, 2*n+1+i+m);
                og.addEdge(2*n+1+i, v+n);
            }
        }
    }

    initTarjan();
    for(int i=1;i<=nm;++i) {
        if(!dfn[i])tarjan(i);
    }

    for(int i=1;i<=n;++i) {
        // printf("%d %c %c\n", i, opts[i].first, opts[i].second);
        if(color[i]==color[i+n]) {
            puts("NO");
            return;
        }
    }


    for(int i=2*n+1;i<=2*n+m;++i) {
        if(color[i]==color[i+m]) {
            puts("NO");
            return;
        }
    }

    puts("YES");

    for(int i=1;i<=n;++i) {
        if(color[i]<color[i+n])putchar(opts[i].second);
        else putchar(opts[i].first);
    }
    puts("");
    /*
    for(int i=2*n+1;i<=2*n+m;++i) {
        if(color[i]<color[i+m])putchar('r');
        else putchar('o');
    }
    puts("");
     */
}


int main() {
    solve();
    return 0;
}
/*
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

4 3
1 2
1 3
1 4
1 2 ab
3 2 aba
1 4 ab
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。