#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <deque>
using namespace std;
const int sigma = 27;
struct aho {
int sz;
vector<int> link;
vector<int> len;
vector<int> p, c;
vector<vector<int>> go;
vector<vector<int>> to;
int freeId = 1;
void reset(int maxc) {
go.resize(maxc);
to.resize(maxc);
for (int i = 0; i < maxc; ++i) {
go[i].assign(sigma, -1);
}
for (int i = 0; i < maxc; ++i) {
to[i].assign(sigma, -1);
}
link.assign(maxc, -1);
len.assign(maxc, 0);
p.assign(maxc, 0);
c.assign(maxc, 0);
freeId = 1;
link[0] = 0;
sz = maxc;
}
void corasickReset() {
for (int i = 0; i < freeId; ++i) {
to[i].assign(sigma, -1);
}
link.assign(freeId, -1);
}
int createNode(int v, char chr) {
len[freeId] = len[v] + 1;
c[freeId] = chr;
p[freeId] = v;
for (int j = 0; j < sigma; ++j) {
go[freeId][j] = -1;
}
link[freeId] = 0;
return freeId++;
}
int extend(char c, int v) {
if (go[v][c] != -1) return go[v][c];
return go[v][c] = createNode(v, c);
}
int lnk(int v) {
if (link[v] == -1) {
if (v == 0 || p[v] == 0) link[v] = 0;
else link[v] = t(lnk(p[v]), c[v]);
}
return link[v];
}
int t(int v, int c) {
if (to[v][c] == -1) {
if (go[v][c] != -1) {
to[v][c] = go[v][c];
} else if (!v) {
to[v][c] = v;
} else {
to[v][c] = t(lnk(v), c);
}
}
return to[v][c];
}
};
int ans = 1;
const int maxn = 50000 + 10;
bool used[maxn];
int sz[maxn];
int treeSize = 0;
string s;
void dfs(int v, vector<vector<int>> &g, int p) {
sz[v] = 1;
for (int u : g[v]) {
if (!used[u] && u != p) {
dfs(u, g, v);
sz[v] += sz[u];
}
}
}
int centroid(int v, vector<vector<int>> &g, int p) {
for (int u : g[v]) {
if (!used[u] && u != p && sz[u] > treeSize / 2) {
return centroid(u, g, v);
}
}
return v;
}
const int P = 29;
const int lg = 16;
const int mod = 1e9 + 7;
int PP[maxn];
vector<aho> bits(lg);
vector<bool> have(lg);
aho curr;
set<int> ids;
void addAll(aho &a, int v1, int v2) {
for (int i = 0; i < sigma; ++i) {
if (a.go[v1][i] != -1 && curr.go[v2][i] == -1) {
curr.go[v2][i] = curr.createNode(v2, i);
}
if (a.go[v1][i] != -1) {
addAll(a, a.go[v1][i], curr.go[v2][i]);
}
}
}
void rebuild() {
for (int i = 0; i < lg; ++i) {
if (!have[i]) {
bits[i] = curr;
have[i] = true;
bits[i].corasickReset();
return;
}
have[i] = false;
addAll(bits[i], 0, 0);
}
}
vector<int> go(char c, vector<int> last) {
for (int i = 0; i < lg; ++i) {
if (have[i]) {
last[i] = bits[i].t(last[i], c);
}
}
return last;
}
int getMaxLen(vector<int> &last) {
int rs = 0;
for (int i = 0; i < lg; ++i) {
if (have[i]) {
rs = max(rs, bits[i].len[last[i]]);
}
}
return rs;
}
void dfs(int v, vector<vector<int>> &g, int p, int h, int hrev, vector<int> last, int len) {
int x = -1;
if (h == hrev) {
ans = max(ans, len);
ids.insert(len);
x = len;
}
h = (h * 1ll * P + s[v]) % mod;
hrev = (hrev + PP[len] * 1ll * s[v]) % mod;
if (h == hrev) {
ans = max(ans, len + 1);
}
last = go(s[v], last);
for (int i = 0; i < lg; ++i) {
if (have[i]) {
int u = last[i];
while (u) {
if (ids.count(len + 1 - bits[i].len[u])) {
ans = max(ans, len + 1 + bits[i].len[u]);
break;
}
u = bits[i].lnk(u);
}
}
}
for (int u : g[v]) {
if (!used[u] && u != p) {
dfs(u, g, v, h, hrev, last, len + 1);
}
}
ids.erase(x);
}
void dfs1(int v, vector<vector<int>> &g, int p, int last) {
last = curr.extend(s[v], last);
for (int u : g[v]) {
if (!used[u] && u != p) {
dfs1(u, g, v, last);
}
}
}
void build(int v, vector<vector<int>> &g) {
dfs(v, g, -1);
treeSize = sz[v];
v = centroid(v, g, -1);
dfs(v, g, -1);
used[v] = 1;
for (int i = 0; i < lg; ++i) {
bits[i].reset(treeSize + 10);
}
have.assign(lg, false);
vector<int> vs(lg, 0);
for (int u : g[v]) {
if (!used[u]) {
dfs(u, g, v, s[v], s[v], go(s[v], vs), 1);
curr.reset(sz[u] + 10);
dfs1(u, g, v, 0);
rebuild();
}
}
reverse(g[v].begin(), g[v].end());
for (int i = 0; i < lg; ++i) {
bits[i].reset(treeSize + 10);
}
have.assign(lg, false);
for (int u : g[v]) {
if (!used[u]) {
dfs(u, g, v, s[v], s[v], go(s[v], vs), 1);
curr.reset(sz[u] + 10);
dfs1(u, g, v, 0);
rebuild();
}
}
for (int u : g[v]) {
if (!used[u]) {
build(u, g);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
PP[0] = 1;
for (int i = 1; i < maxn; ++i) {
PP[i] = (PP[i - 1] * 1ll * P) % mod;
}
int n;
cin >> n;
cin >> s;
for (int i = 0; i < n; ++i) {
s[i] = s[i] - 'a' + 1;
}
vector<vector<int>> g(n);
for (int i = 0; i + 1 < n; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
build(0, g);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
342 ms |
472920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
407 ms |
524288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
