#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e5 + 5;
const int base = 31;
const int mod = 1e9 + 9;
int p[maxn];
vector<int> g[maxn];
int n, a[maxn];
string s;
bool del[maxn];
int sz[maxn];
vector<pair<int, int>> save;
map<int, bool> mp[maxn];
int path_len, max_dep;
bool exist;
int find_centroid(int u, int prev, int n) {
for(auto v:g[u]) {
if(!del[v] and v != prev and sz[v] * 2 > n)
return find_centroid(v, u, n);
}
return u;
}
void re_dfs(int u, int prev) {
sz[u] = 1;
for(auto v:g[u]) {
if(v == prev || del[v]) continue;
re_dfs(v, u);
sz[u] += sz[v];
}
}
void dfs_upd(int u, int prev, int dep, int hu, int hd) {
if(dep > path_len)
return;
hd = (1ll * hd * base + (s[u] - 'a' + 1)) % mod;
hu = (hu + 1ll * p[dep - 1] * (s[u] - 'a' + 1) % mod) % mod;
int x = (1ll * hu * p[path_len - dep] % mod - hd + mod) % mod;
mp[dep][x]++;
for(auto v:g[u]) {
if(del[v] || v == prev) continue;
dfs_upd(v, u, dep + 1, hu, hd);
}
}
bool dfs_get(int u, int prev, int dep, int hu, int hd) {
if(dep > path_len)
return 0;
if(prev)
hd = (1ll * hd * base + (s[u] - 'a' + 1)) % mod;
hu = (hu + 1ll * p[dep - 1] * (s[u] - 'a' + 1) % mod) % mod;
int x = (1ll * hu * p[path_len - dep] % mod - hd + mod) % mod;
if(!prev)
mp[dep][x] = 1;
if(mp[path_len - dep + 1].count(x)) {
return 1;
}
for(auto v:g[u]) {
if(del[v] || v == prev) continue;
if(dfs_get(v, u, dep + 1, hu, hd))
return 1;
if(!prev) {
for(auto i:save) {
mp[i.first][i.second] = 1;
}
}
}
max_dep = max(dep, max_dep);
save.push_back({dep, x});
return 0;
}
void decompose(int u, int prev) {
if(exist)
return;
re_dfs(u, prev);
int c = find_centroid(u, prev, sz[u]);
exist |= dfs_get(c, 0, 1, 0, 0);
for(int i = 1; i <= max_dep; ++i) {
mp[i].clear();
}
max_dep = 0;
del[c] = 1;
for(auto v:g[c]) {
if(del[v]) continue;
decompose(v, c);
}
}
bool check(int mid) {
path_len = mid;
memset(del, 0, sizeof(del));
exist = 0;
decompose(1, 0);
// debug(mid, exist);
return exist;
}
void solve() {
cin >> n >> s;
s = ' ' + s;
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int res = 1;
int l = 1, r = (n - 1) / 2;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid * 2 + 1)) {
res = max(res, mid * 2 + 1);
l = mid + 1;
}
else {
r = mid - 1;
}
}
l = 1, r = n / 2;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid * 2)) {
res = max(res, mid * 2);
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
p[0] = 1;
for(int i = 1; i < maxn; ++i) {
p[i] = 1ll * p[i - 1] * base % mod;
}
solve();
return 0;
}
Compilation message
lampice.cpp: In function 'void dfs_upd(int, int, int, int, int)':
lampice.cpp:50:13: error: use of an operand of type 'bool' in 'operator++' is forbidden in C++17
50 | mp[dep][x]++;
| ^~
