Codeforces GM题目泛做
在一个无向连通图上，边有黑白之分；找到一个简单环，使得其经过了所有的黑边仅一次。
$n,m\leq 5*10^5$
和ABC286G非常相似的题目，只不过多了一个简单环的限制。
实际上这个限制仅对最后输出结果有用。
暂时先不考虑白边的走法，相当于把白边缩点，这样图上只剩下黑边；判定这个图是否存在欧拉回路即可。
接下来考虑如何构造这个简单环。
首先白边缩点之后，每个点度数均为偶数，考虑黑边的实际意义，相当于从白色大点的$u_1$走入，$u_2$走出，$u_3$走入，$u_4$走出，且每条边仅能走一次。
这样我们要合理配对走入和走出的点，使其路径不相交。
考虑树上路径异或的构造方法。造出白色大点的一个生成树。
我们对$u_1$和$u_2$的路径进行一次异或，$u_3$和$u_4$的路径进行一次异或。这样最后我们发现边权为1的边，构成了若干不相交的路径（因为相交一次即为异或两次1，结果不变）。路径异或可以用点权异或替代，那么这个问题就解决了。
这样我们发现把所有黑边和树上边权为1的边都拿出来，这个图一定还是欧拉回路图。因为树上路径中，点一定被经过偶数次，同理依然每个点度数为偶数。
只需要对这个图做一次欧拉回路即可。复杂度$O(n+m)$。
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
|
int Main()
{
int n, m;
read(n, m);
std::vector<int> c(m + 1);
std::vector<std::pair<int, int>> edge(m + 1);
for (int i = 1; i <= m; ++i)
{
auto &[u, v] = edge[i];
read(u, v, c[i]);
}
DSU dsu(n);
std::vector tree(n + 1, std::vector<std::pair<int, int>>{});
for (int i = 1; i <= m; ++i)
{
if (c[i] == 1)
continue;
auto [u, v] = edge[i];
if (!dsu.same(u, v))
{
dsu.merge(u, v);
tree[u].push_back({v, i});
tree[v].push_back({u, i});
}
}
std::vector<int> d(n + 1);
std::vector e(n + 1, std::vector<int>{});
for (int i = 1; i <= m; ++i)
{
if (c[i] == 0)
continue;
auto [u, v] = edge[i];
int root_u = dsu.leader(u);
int root_v = dsu.leader(v);
d[root_u]++, d[root_v]++;
e[root_u].push_back(u), e[root_v].push_back(v);
}
for (int i = 1; i <= n; ++i)
{
if (i == dsu.leader(i))
{
if (d[i] % 2 != 0)
return printf("NO\n"), 0;
}
}
std::vector<int> tag(n + 1);
auto dfs = [&](auto &&self, int u, int fa) -> void
{
for (auto [v, i] : tree[u])
{
if (v == fa)
continue;
self(self, v, u);
tag[u] ^= tag[v];
if (tag[v] == 1)
c[i] = 1;
}
};
for (int i = 1; i <= n; ++i)
{
if (i == dsu.leader(i))
{
for (int j = 0; j < e[i].size(); j += 2)
{
int u = e[i][j], v = e[i][j + 1];
tag[u] ^= 1, tag[v] ^= 1;
}
dfs(dfs, i, 0);
}
}
std::vector adj(n + 1, std::vector<std::pair<int, int>>{});
for (int i = 1; i <= m; ++i)
{
if (c[i] == 1)
{
auto [u, v] = edge[i];
adj[u].push_back({v, i}), adj[v].push_back({u, i});
// printf("%d %d\n", u, v);
}
}
std::vector<int> vis(m + 1);
std::vector<int> cur(n + 1);
auto euler_tour = [&](auto &&self, int u, std::vector<int> &res) -> void
{
for (int &k = cur[u]; k < adj[u].size(); ++k)
{
auto [v, i] = adj[u][k];
if (vis[i])
continue;
vis[i] = true;
self(self, v, res);
}
res.push_back(u);
};
std::vector<int> ans{};
euler_tour(euler_tour, dsu.leader(1), ans);
printf("YES\n%d\n", ans.size() - 1);
for (int u : ans)
printf("%d ", u);
printf("\n");
return 0;
}
|
一张无向完全图，有点权p_i；边$(u,v)$的边权是$max(p_u, p_v) \bmod min(p_u, p_v)$，求最小生成树
$n\leq 500000$,$p_i\leq 500000$
不妨假设$p_u < p_v$。
那么$p_v$必然落在$p_u$的某一个倍数区间$[k*p_u, (k+1)*p_u-1]$内。
假设$v,x$两个点都落在同一个区间内，那么如果$p_v< p_x$，则从$u$到$x$的连边可以不予考虑；因为我们只需要选$u,v$和$v,x$两条边就能使它连通。
因此对$p_u$来说，对其真正有用的是区间$[k*p_u, (k+1)*p_u-1]$内最小点权的那个点，那么总边数就不超过$O(PlogP)$条
接下来就是普通MST了。
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
|
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
int mx = *std::max_element(a.begin(), a.end());
std::vector p(mx + 1, std::vector<int>{});
for (int i = 1; i <= n; ++i)
p[a[i]].push_back(i);
std::vector<int> next(mx + 1);
for (int i = mx; i >= 1; --i)
{
if (i + 1 <= mx)
{
if (p[i + 1].size())
next[i] = i + 1;
else
next[i] = next[i + 1];
}
}
std::vector buc(mx + 1, std::vector<std::pair<int, int>>{});
for (int i = 1; i <= mx; ++i)
{
if (p[i].size() == 0)
continue;
int u = p[i][0];
for (int j = i; j <= mx; j += i)
{
for (int v : p[j])
buc[0].push_back({u, v});
int w = next[j];
if (w - j < i)
{
for (int v : p[w])
buc[w - j].push_back({u, v});
}
}
}
DSU dsu(n);
ll ans = 0;
for (int w = 0; w <= mx; ++w)
{
for (auto [u, v] : buc[w])
{
// printf("%d %d %d\n", u, v, w);
if (!dsu.same(u, v))
{
ans += w;
dsu.merge(u, v);
}
}
}
printf("%lld\n", ans);
return 0;
}
|
给出$n$和$m$，求所有满足$\sum_{i=1}^m a_i = n$的序列中，所有可能出现的序列异或和之和。一个异或值出现多次仅被计数一次。
多测$t\leq 10^5, n\leq 10^{18}, m\leq 10^5$
大概看数据规模，感觉最终复杂度跟$m$无关。
可能有一些简单的结论。
首先可以明确的是，异或和的奇偶性应该和$n$是相同的。因为异或操作在单个位上等价于加法对2取模。
当$m=1$时，显然就是$n$本身，注意答案应该对998244353取模；
当$m=2$时，感觉可以数位DP。
当$m=3$时，因为可以写成$a+b+b$的形式，所以所有比$n$小的，奇偶性相同的数都能取到。
$m>3$时，令多余的数为0，变成$m=3$的情况。
所以只需要对$m=2$时做特殊数位DP即可。
设$dp[i][c][0]$表示前$i$位，目前进位为$c$，和与$n$相等的异或值的数量；$dp[i][c][1]$表示这些异或值的总和。
枚举$a_1$和$a_2$在这一位的取值，因为去重的关系只有00,11,10三种取值。
由于进位会影响高位的决策，即假设$a\oplus b=c\oplus d$，但$a+b$多了一个进位，那么在高一位的地方，$a\oplus b$的取值和$c\oplus d$的取值将会相反；因此00和11虽然在异或值上相同，考虑到更高位，不会造成计数重复。
转移是简单的，那么这道题就完美做掉了。
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
|
modint dp[65][2][2];
int Main()
{
ll n, m;
read(n, m);
if (m >= 3)
{
ll k = n / 2;
ll a = n % 2;
printf("%lld\n", modint{a + a + k * 2} * (k + 1) / 2);
return 0;
}
if (m == 1)
return printf("%lld\n", modint{n}), 0;
memset(dp, 0, sizeof(dp));
dp[0][0][1] = 0, dp[0][0][0] = 1;
for (int i = 0; i <= 60; ++i)
{
int N = (n >> i) & 1;
for (int c = 0; c < 2; ++c)
{
// 00
if (N == c)
{
dp[i + 1][0][0] += dp[i][c][0];
dp[i + 1][0][1] += dp[i][c][1];
}
// 11
if (N == c)
{
dp[i + 1][1][0] += dp[i][c][0];
dp[i + 1][1][1] += dp[i][c][1];
}
// 01
if (N == (c ^ 1))
{
dp[i + 1][(c + 1) / 2][0] += dp[i][c][0];
dp[i + 1][(c + 1) / 2][1] += modint{1ll << i} * dp[i][c][0] + dp[i][c][1];
}
}
}
printf("%d\n", dp[61][0][1]);
return 0;
}
|
给出$n$个二进制串$a[i]$和一个二进制串$s$；求使得$\sum_{i=1}^n a[i]\oplus x=s$的任意$x$
传统竖式数位DP艺能了属于是。
$dp[i][c]$表示前$i$位目前进位为$c$是否存在$x$，直接枚举这一位$x$的取值，转移即可。
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
|
int Main()
{
int n, k;
std::cin >> n >> k;
std::string s;
std::cin >> s;
std::vector<std::string> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::reverse(s.begin(), s.end());
for (int i = 1; i <= n; ++i)
std::reverse(a[i].begin(), a[i].end());
std::vector dp(k + 1, std::vector<uint8_t>(n + 1));
std::vector pre(k + 1, std::vector<int>(n + 1));
std::vector d(k + 1, std::vector<uint8_t>(n + 1));
dp[0][0] = true;
for (int i = 0; i < k; ++i)
{
int zero = 0;
for (int j = 1; j <= n; ++j)
zero += a[j][i] == '0';
for (int carry = 0; carry <= n; ++carry)
{
if (!dp[i][carry])
continue;
// x = 0
int sum = carry + n - zero;
if ((sum & 1) == s[i] - '0')
{
dp[i + 1][sum >> 1] = true;
d[i + 1][sum >> 1] = 0;
pre[i + 1][sum >> 1] = carry;
}
// x = 1
sum = carry + zero;
if ((sum & 1) == s[i] - '0')
{
dp[i + 1][sum >> 1] = true;
d[i + 1][sum >> 1] = 1;
pre[i + 1][sum >> 1] = carry;
}
}
}
if (!dp[k][0])
printf("-1\n");
else
{
for (int i = k, c = 0; i >= 1; --i)
{
putchar('0' + d[i][c]);
c = pre[i][c];
}
putchar('\n');
}
return 0;
}
|
将一个长度为$n$的数组$a$分成若干连续段，使得每段的或和单调不降；求方案数
考虑普通DP。有$dp[i][x]$为目前分到$i$，最后一段的或和是$x$的方案数。
鉴于以任意点为右端点的或和，不会超过$log_2(V=max{ a[i]})$个不同的值，且值向左呈现单调递增的特性，则左端点会形成$log_2(max{ a[i]})$个区间，每个区间内的左端点到$i$的或和都是相同的。
则有$dp[i][x]=\sum_{j=l_k}^{r_k} \sum_{y=0}^x dp[j][y]$形成一个二维数点问题。
朴素的想法可以使用可持久化线段树维护值域这一维，查询时找到对应区间的可持久化线段树做差分即可。
但是一共有$O(nlog_2V)$个数点，可持久化线段树额外还有$O(log_2V)$的空间复杂度，因此空间复杂度过高。
考虑离线处理这个DP。离散化所有可能的或值，并按或值大小来做扫描线。那么只需要查询一个简单的区间和即可，树状数组就可以实现。
时间复杂度为$O(nlog_2Vlog_2n)$
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
|
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::array<int, 31> pre{};
// pre[0].fill(-1);
std::vector key(n + 1, std::vector<int>{});
std::vector v(n + 1, std::vector<int>{});
std::vector<int> buc{0};
{
SparseTable<int, std::bit_or<int>> st(a, n);
for (int i = 1; i <= n; ++i)
{
for (int p = 0; p < 30; ++p)
{
if (a[i] & (1 << p))
pre[p] = i;
if (pre[p])
key[i].push_back(pre[p]);
}
key[i].push_back(i);
std::sort(key[i].begin(), key[i].end());
key[i].erase(std::unique(key[i].begin(), key[i].end()), key[i].end());
v[i].resize(key[i].size());
for (int x = 0; x < key[i].size(); ++x)
{
v[i][x] = st.query(key[i][x], i);
buc.emplace_back(v[i][x]);
}
}
}
std::sort(buc.begin(), buc.end());
buc.erase(std::unique(buc.begin(), buc.end()), buc.end());
for (int i = 1; i <= n; ++i)
for (int x = 0; x < key[i].size(); ++x)
{
v[i][x] = std::lower_bound(buc.begin(), buc.end(), v[i][x]) - buc.begin();
}
// PersistentSegmentTree<modint> segment_tree(buc.size());
// std::vector<int> root(n + 1);
// root[0] = segment_tree.modify(root[0], 1, 1);
std::array<modint, 31> dp{};
std::vector qry(buc.size(), std::vector<std::array<int, 3>>{});
for (int i = 1; i <= n; ++i)
{
int l = 0;
// root[i] = root[i - 1];
// dp.fill(0);
for (int j = 0; j < key[i].size(); ++j)
{
int r = key[i][j];
int x = v[i][j];
qry[x].push_back({i, l, r - 1});
l = r;
}
}
FenwickTree<modint> fwt(n + 1);
fwt.modify(0, 1);
modint ans = 0;
for (int line = 0; line < buc.size(); ++line)
{
for (auto [i, l, r] : qry[line])
{
modint res = fwt.query(r);
if (l > 0)
res -= fwt.query(l - 1);
if (i == n)
ans += res;
fwt.modify(i, res);
}
}
// modint ans = std::accumulate(dp.begin(), dp.end(), modint{0});
printf("%d\n", ans);
return 0;
}
|
给出一个长度为$n$的数组$a[i]$，每个数的范围都是$[1,k]$。请问有多少个长度为$m$的数组$b$，元素同样范围是$[1,k]$，包含$a$为一个子序列。
$n\leq 2*10^5, n\leq m\leq 10^9, 1\leq k\leq 10^9$
首先考虑$b$包含$a$为子序列是怎么判定的？
可以通过子序列自动机——找到每个$b[i]$后面第一个$x$出现的位置，贪心地匹配。
也就是说$b$数组要能在$m$位之前匹配$a$数组作为子序列。
所以我们考虑$a[1\cdots i]$在$b$中第一次出现的位置$j$和$a[1\cdots i-1]$在$b$中第一次出现的位置$p$，则$p+1,j-1$处只有$a[i]$是不能出现的，否则$j$就不是第一次出现的位置的。换句话说除了$a[1\cdots i]$在$b$中第一次出现的匹配位之外，在未匹配完成的地方每个位置是$k-1$种选择；匹配完成后每个位置是$k$种选择。
考虑枚举匹配完成的位置$x$，则方案数为$\sum_{x=n}^m k^{m-x} * C_{x-1}^{n-1} (k-1)^{x-n}$
感觉不是很优雅，因为匹配完成之后和匹配完成之前的方案出现了$k-1$和$k$的偏差。
怎样能让每个非匹配位的选择是固定的呢？
那么可以考虑让匹配不成功，最后用总方案减去错误方案。
那这样的话可以枚举$b$最终匹配到的$a[i]$位置，选出$i$个位置和$a[i]$匹配，剩下的所有位置都是$k-1$种方案。
这样的话答案就是$k^m-\sum_{i=1}^n C_m^i (k-1)^{m-i}$。
通过倒序处理$\frac{m!}{(m-i)!}$的技巧，可以在$O(n)$时间内完成计算。
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
|
int Main()
{
int n, m, k;
read(n, m, k);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
Combinatorics<modint> c(n);
std::vector<modint> fm(n + 1);
fm[0] = 1;
for (int i = 1; i <= n; ++i)
fm[i] = fm[i - 1] * (m - i + 1);
std::vector<modint> pw(n + 1);
if (k - 1)
{
pw[0] = modint{k - 1}.pow(m);
modint invk_1 = modint{k - 1}.inv();
for (int i = 1; i <= n; ++i)
pw[i] = pw[i - 1] * invk_1;
}
modint wa = 0;
for (int i = 0; i < n; ++i)
wa += fm[i] * c.invfac[i] * pw[i];
modint all = modint{k}.pow(m);
modint ans = all - wa;
printf("%d\n", ans);
return 0;
}
|
对于一段序列$a[1\cdots n]$，可以选择一个分界线，将其分割成左右两部分，并保留异或和大的那部分；若相等则都可以保留。
$n\leq 10000, a_i < 2^{60}$
首先$O(n^3)$的DP是显然的。
$dp[l][r]$表示$[l,r]$区间是否可以达。枚举分界线$k$即可递推。
超时是显然的，不妨考虑如何快速选出想要的$k$。
即$sum^k \oplus sum_{l-1} > sum^k \oplus sum_{r}$
两个二进制数如果能比出大小，他们必然会有一段LCP，并在LCP+1处出现差异。即$sum_{l-1}$和$sum_r$第一次出现差异的地方，也就是$msb(sum_r \oplus sum_{l-1})$。只要$sum_k$和$sum_{l-1}$的异或值在$msb$处是1，$dp[l][k]$即可取到。
所以我们现在可以对$[l,r]$区间内的每个一个$k$打一个这样的标记；注意到一点，当我们在计算$dp[l][r]$时，区间长度是递减的，则接下来所有$dp[l][x]$的出现，$x$都是$[l,r]$区间内的。所以我们只需要在$l$处打一个这样的标记即可。
反过来也是一样的。
相等的情况稍微不太一样，因为可能会出现$0$值，所以我们额外在61位设定一个万能位，只要能匹配万能位即可判定成功。
复杂度$O(n^2)$，有$\frac{1}{2}$的常数。
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
|
int Main()
{
int n;
read(n);
std::vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::vector dp(n + 1, std::vector<int>{});
for (int i = 1; i <= n; ++i)
dp[i].resize(n - i + 2);
dp[n][1] = true;
std::vector<ll> sum(n + 1);
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] ^ a[i];
ll allmask = (1ll << 61);
std::vector<std::array<ll, 2>> mask(n + 1);
{
int p = msb(sum[n]);
if (p >= 0)
{
mask[1][0] |= (1ll << p);
mask[n][1] |= (1ll << p);
}
else
mask[1][0] = mask[n][1] = allmask;
}
for (int len = n - 1; len >= 1; --len)
{
for (int i = 1; i <= n - len + 1; ++i)
{
int j = i + len - 1;
if ((allmask | sum[i - 1] ^ sum[j]) & (mask[j][1]))
dp[len][i] |= true;
if ((allmask | sum[i - 1] ^ sum[j]) & (mask[i][0]))
dp[len][i] |= true;
if (dp[len][i])
{
int p = msb(sum[j] ^ sum[i - 1]);
if (p < 0)
mask[i][0] = mask[j][1] |= allmask;
else
mask[i][0] |= (1ll << p), mask[j][1] |= (1ll << p);
}
// printf("dp[%d][%d] = %d\n", i, j, dp[len][i]);
// printf("mask[%d][0] = %d\n", 1, mask[1][0]);
}
}
for (int i = 1; i <= n; ++i)
if (dp[1][i])
printf("1");
else
printf("0");
printf("\n");
return 0;
}
|
一棵$n$个节点的无向树，给出了$q$个条件。
每个询问给出两个点$u,v$和字符串$s$，确保$s$的长度和$u,v$路径长度一致。
这个字符串要么按从$u->v$的顺序，要么按从$v->u$的顺序。
求问是否有一组给各个节点分配字母的方案，满足所有$q$个条件
$n,q,\sum |s|\leq 4*10^5$
时隔十三年再见2-SAT。
$q_0$表示正序，$q_1$表示逆序，显然能得到一个对于单个$q$二者互斥的结论。
另外，根据各节点的字符的相等性可以划分出各个变量之间的互斥关系。
但是直接暴力去搞显然是$O(q^2)$的边数。此时考虑图论中的“传递优化”。
鉴于我们使用各节点的字符取值来刻画变量之间的互斥关系，不妨将各节点的字符取值也刻画为一个变量。
设$u_c$表示$u$节点是否取到$c$这个字符。首先$u$节点本身有一个$O(26^2)$的互斥关系。接下来考虑将$q_0$和$q_1$和$u_c$之间连边，这样就传递了$q$之间的关系。
但是边数还是有点多，不过题目给了9s的时限是可以过的。
考虑一个有趣的事实是：如果一个节点有超过2种取值，那么不管怎样都无解。
所以每个节点我们只保留两种取值，定为$u_0$和$u_1$。这样节点也变成了一个二元取值的变量，和普通2-SAT无异。
于是边数和点数都是$O(n+q+\sum|s|)$级别。
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
|
int Main()
{
int n, q;
std::cin >> n >> q;
HLD tree(n);
for (int i = 1; i < n; ++i)
{
int u, v;
std::cin >> u >> v;
tree.add_edge(u, v);
}
tree.build();
std::vector ans(n + 1, std::array<char, 2>{'a', 'z'});
std::vector<std::tuple<int, int, std::string>> qry(q + 1);
for (int i = 1; i <= q; ++i)
{
auto &[u, v, s] = qry[i];
std::cin >> u >> v >> s;
int lca = tree.lca(u, v);
for (int j = 0, p = u; j < s.length() && p != tree.fa[lca]; p = tree.fa[p], ++j)
{
ans[p][0] = s[j];
ans[p][1] = s[s.length() - j - 1];
}
for (int j = s.length() - 1, p = v; j >= 0 && p != lca; p = tree.fa[p], --j)
{
ans[p][0] = s[j];
ans[p][1] = s[s.length() - j - 1];
}
}
TwoSat G(n + q);
for (int i = 1; i <= q; ++i)
{
auto [u, v, s] = qry[i];
int lca = tree.lca(u, v);
for (int j = 0, p = u; j < s.length() && p != tree.fa[lca]; p = tree.fa[p], ++j)
{
if (ans[p][0] != s[j])
G.add_clause(p, 1, i + n, 1);
if (ans[p][0] != s[s.length() - j - 1])
G.add_clause(p, 1, i + n, 0);
if (ans[p][1] != s[j])
G.add_clause(p, 0, i + n, 1);
if (ans[p][1] != s[s.length() - j - 1])
G.add_clause(p, 0, i + n, 0);
}
for (int j = s.length() - 1, p = v; j >= 0 && p != lca; p = tree.fa[p], --j)
{
if (ans[p][0] != s[j])
G.add_clause(p, 1, i + n, 1);
if (ans[p][0] != s[s.length() - j - 1])
G.add_clause(p, 1, i + n, 0);
if (ans[p][1] != s[j])
G.add_clause(p, 0, i + n, 1);
if (ans[p][1] != s[s.length() - j - 1])
G.add_clause(p, 0, i + n, 0);
}
}
bool sat = G.satisfiable();
if (sat)
{
printf("YES\n");
auto res = G.answer();
for (int i = 1; i <= n; ++i)
putchar(ans[i][res[i]]);
putchar('\n');
}
else
printf("NO\n");
return 0;
}
|