#include <bits/stdc++.h>
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int MAX = 50005;
int n, k;
string s;
int sz[MAX];
bool rem[MAX];
vector<int> adj[MAX];
const int MOD = 1e9 + 7;
const int BASE = 256;
int pw[MAX];
int dfsSZ(int u, int p) {
sz[u] = 1;
for (int v: adj[u]) if (v != p && !rem[v]) {
sz[u] += dfsSZ(v, u);
}
return sz[u];
}
int findCentroid(int u, int p, int n) {
for (int v: adj[u]) if (v != p && !rem[v]) {
if (2 * sz[v] > n)
return findCentroid(v, u, n);
}
return u;
}
int h[MAX];
int maxHigh;
int hashU[MAX];
int hashD[MAX];
int value[MAX];
int nNode, node[MAX];
map<int, bool> mp[MAX];
void add(int u, int p, bool &found) {
h[u] = h[p] + 1;
if (h[u] + 1 > k) return;
maxHigh = max(maxHigh, h[u]);
hashU[u] = (1LL * hashU[p] * BASE + (a[u] - 'a' + 1)) % MOD;
hashD[u] = (hashD[p] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD;
int need = (1LL * pw[k - h[u] - 1] * hashD[u] - hashU[u] + MOD) % MOD;
if (mp[k - h[u] - 1].find(need) != mp[k - h[u] - 1].end()) {
found = true;
return;
}
if (h[u] + 1 == k && hashD[u] == (hashU[u] + 1LL * pw[h[u]] * (a[u] - 'a' + 1)) % MOD) {
found = true;
return;
}
node[++nNode] = u; value[u] = need;
for (int v: adj[u]) if (v != p && !rem[v]) {
add(v, u, found);
if (found) return;
}
}
void solve(int u, int p, bool &found) {
int n = dfsSZ(u, p), c = findCentroid(u, p, n); rem[c] = true;
h[c] = 0;
nNode = 0;
maxHigh = 0;
hashU[c] = 0;
hashD[c] = a[c] - 'a' + 1;
for (int v: adj[c]) if (v != p && !rem[v]) {
add(v, c, found);
if (found) return;
while (nNode > 0) {
int u = node[nNode--];
mp[h[u]][value[u]] = 1;
}
}
for (int i = 0; i <= maxHigh; ++i) {
mp[i].clear();
}
for (int v: adj[c]) if (v != p && !rem[v]) {
solve(v, c, found);
if (found) return;
}
}
bool func(int x) {
memset(rem, false, sizeof rem);
bool found = false; k = x;
solve(1, 0, found);
return found;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> a;
a = "@" + a;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
pw[i] = (pw[i - 1] * BASE) % MOD;
}
int ans = 1;
for (int i = 0; i <= 1; ++i) {
int l = 0, r = n / 2 + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (func(i + 2 * mid))
l = mid;
else
r = mid;
}
ans = max(ans, i + 2 * l);
}
cout << ans << "\n";
return 0;
}
Compilation message
lampice.cpp: In function 'void add(int, int, bool&)':
lampice.cpp:46:46: error: 'a' was not declared in this scope
46 | hashU[u] = (1LL * hashU[p] * BASE + (a[u] - 'a' + 1)) % MOD;
| ^
lampice.cpp: In function 'void solve(int, int, bool&)':
lampice.cpp:71:20: error: 'a' was not declared in this scope
71 | hashD[c] = a[c] - 'a' + 1;
| ^
lampice.cpp: In function 'int main()':
lampice.cpp:105:21: error: 'a' was not declared in this scope
105 | cin >> n >> a;
| ^
lampice.cpp:101:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:102:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
