#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ll long long
const int maxn = 5e4 + 6;
using namespace std;
using namespace __gnu_pbds;
const int base = 311;
int n;
basic_string<int> edges[maxn];
int ans = 1;
char a[maxn];
gp_hash_table<ll, bool> m;
struct Hash {
ll pw[maxn], hash_val[maxn], pre_hash[maxn];
int n;
void prepare(int sz) {
n = 0;
pw[0] = 1;
for (int i = 1; i <= sz; ++i)
pw[i] = pw[i - 1] * base;
}
void push(char c) {
n++;
hash_val[n] = hash_val[n - 1] * base + c;
pre_hash[n] = pre_hash[n - 1] + c * pw[n - 1];
}
void pop() {
n--;
}
void clear() {
n = 0;
}
bool IsPalin(int l) {
return hash_val[l] == pre_hash[l];
}
ll get(int l) {
return hash_val[n] - hash_val[n - l] * pw[l];
}
} hs;
struct CD {
int sz[maxn];
bool del[maxn];
void init() {
memset(del, 0, sizeof(del)); // nhanh hơn vòng for
}
void dfs(int u, int p) {
sz[u] = 1;
for (int v : edges[u])
if (v != p && !del[v]) {
dfs(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int p, int total_size) {
for (int v : edges[u])
if (v != p && !del[v] && sz[v] > total_size / 2)
return find_centroid(v, u, total_size);
return u;
}
bool get(int u, int p, int height, int len) {
hs.push(a[u]);
if (2 * height <= len && m[hs.get(height)]) return true;
if (height == len && hs.IsPalin(len)) return true;
for (int v : edges[u])
if (v != p && !del[v])
if (get(v, u, height + 1, len)) return true;
hs.pop();
return false;
}
bool update(int u, int p, int height, int len) {
hs.push(a[u]);
if (height * 2 >= len && hs.IsPalin(height * 2 - len))
m[hs.get(len - height)] = 1;
if (height == len && hs.IsPalin(len)) return true;
for (int v : edges[u])
if (v != p && !del[v])
if (update(v, u, height + 1, len)) return true;
hs.pop();
return false;
}
bool decompose(int u, int len) {
dfs(u, 0);
int total_size = sz[u];
int c = find_centroid(u, 0, total_size);
del[c] = 1;
for (int turn = 1; turn <= 2; ++turn) {
m.clear();
for (int v : edges[c]) {
if (!del[v]) {
hs.clear();
if (get(v, c, 1, len)) return true;
hs.clear();
hs.push(a[c]);
if (update(v, c, 2, len)) return true;
}
}
reverse(edges[c].begin(), edges[c].end()); // để đảm bảo không bỏ sót cạnh nào
}
for (int v : edges[c])
if (!del[v])
if (decompose(v, len)) return true;
return false;
}
} cd;
void tknp(int l, int r, int ok) {
while (l <= r) {
int mid = (l + r) >> 1;
cd.init();
if (cd.decompose(1, 2 * mid + ok))
maximize(ans, 2 * mid + ok), l = mid + 1;
else
r = mid - 1;
}
}
void solve() {
cin >> n;
hs.prepare(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
tknp(1, n >> 1, 0);
tknp(1, n >> 1, 1);
cout << ans << endl;
}
int32_t main() {
faster;
solve();
return 0;
}
Compilation message
lampice.cpp: In function 'void tknp(int, int, int)':
lampice.cpp:139:13: error: 'maximize' was not declared in this scope
139 | maximize(ans, 2 * mid + ok), l = mid + 1;
| ^~~~~~~~
