[Gym100543G] Virus synthesis

题面:
https://codeforces.com/gym/100543/attachments/download/2854/20142015-acmicpc-central-europe-regional-contest-cerc-14-en.pdf

题目大意

输入一个长度为 \(n\) 的字符串 \(s\)。你有一个空串 \(t\),你要把它变成输入的字符串。可以进行以下几种操作:

  • \(t\) 的开头或者末尾添加一个字符。
  • \(t\) 翻转过来,然后接在原来的 \(t\) 的开头或末尾。

求最少操作次数。
\(n \le 10^5\)

解法

在最后连续的若干次加字符操作之前,\(t\) 一定是回文串。倒过来考虑,用最少操作次数把 \(s\) 变成空串。只需要分别考虑每个回文串的最少操作次数。

建立回文树。只需要考虑三种转移:

  • 一个长度为偶数的回文串变为他的一半。
  • 一个回文串,去掉他两端的字符。
  • 一个回文串,转移到他的最长回文前缀。

按长度从小到大顺序 \(dp\)。后两种转移可以直接计算。对第一种转移,倍增一下判断 \(fail\) 树上有没有长度恰好为一半的祖先即可。

代码

下面的代码是假的。要省选了..先补点别的再来打这题QAQ。

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200010;
const ll inf = 1e18;

int c[maxn], vis[4*maxn], n;
ll dp[maxn][2][2];
vector<int> tree[maxn], tran[maxn*4];

void dfs1(int u, int f) {
dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = inf;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f) {
dfs1(v, u);
}
}
if (u == 1 || tree[u].size() > 1) {
ll s = 0, mn = inf, cm = inf;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f) {
s += min(dp[v][0][0], dp[v][1][0]);
ll t = dp[v][0][1] - min(dp[v][0][0], dp[v][1][0]);
if (t <= mn) {
cm = mn;
mn = t;
} else if (t < cm)
cm = t;
}
}
dp[u][0][0] = s;
dp[u][0][1] = s+mn;
dp[u][1][0] = min(s+c[u]+mn, s+c[u]);
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f) {
if (dp[v][0][0] < dp[v][1][0]) {
tran[u*4+2*0+0].push_back(v*4+2*0+0);
if (mn >= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
} else if (dp[v][0][0] > dp[v][1][0]) {
tran[u*4+2*0+0].push_back(v*4+2*1+0);
if (mn >= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
} else {
tran[u*4+2*0+0].push_back(v*4+2*0+0);
tran[u*4+2*0+0].push_back(v*4+2*1+0);
if (mn >= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
if (mn >= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
}
ll t = dp[v][0][1] - min(dp[v][0][0], dp[v][1][0]);
if (t == mn) {
if (mn == cm) {
if (dp[v][0][0] < dp[v][1][0]) {
tran[u*4+2*0+1].push_back(v*4+2*0+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
} else if (dp[v][0][0] > dp[v][1][0]) {
tran[u*4+2*0+1].push_back(v*4+2*1+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
} else {
tran[u*4+2*0+1].push_back(v*4+2*0+0);
tran[u*4+2*0+1].push_back(v*4+2*1+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
}
}
tran[u*4+2*0+1].push_back(v*4+2*0+1);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*0+1);
} else {
if (dp[v][0][0] < dp[v][1][0]) {
tran[u*4+2*0+1].push_back(v*4+2*0+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
} else if (dp[v][0][0] > dp[v][1][0]) {
tran[u*4+2*0+1].push_back(v*4+2*1+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
} else {
tran[u*4+2*0+1].push_back(v*4+2*0+0);
tran[u*4+2*0+1].push_back(v*4+2*1+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*0+0);
if (mn <= 0) tran[u*4+2*1+0].push_back(v*4+2*1+0);
}
}
}
}
} else {
dp[u][1][0] = c[u];
dp[u][0][1] = 0;
}
}

void dfs2(int u) {
vis[u] = 1;
for (int i = 0; i < tran[u].size(); i++) {
int v = tran[u][i];
if (!vis[v])
dfs2(v);
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs1(1, 0);
int cnt = 0;
ll ans = min(dp[1][0][0], dp[1][1][0]);
printf("%lld ", ans);
if (dp[1][0][0] == ans) dfs2(4*1+2*0+0);
if (dp[1][1][0] == ans) dfs2(4*1+2*1+0);
for (int i = 1; i <= n; i++) {
if (vis[4*i+2*1+0] || vis[4*i+2*1+1]) {
cnt ++;
}
}
printf("%d\n", cnt);
for (int i = 1; i <= n; i++) {
if (vis[4*i+2*1+0] || vis[4*i+2*1+1]) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}