#include <bits/stdc++.h>
#define debug cout << "fuck\n";
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 2e5 + 5;
const long long base = 311;
const long long MOD = 2e9 + 7;
ll H[N], rH[N], pw[N], h[N], up[20][N];
vector <int> d[N], centroid;
string SS;
int n, numchild[N], s[N];
bool dead[N];
// find centroid
int get_size(int p, int u) {
int ans = 1;
for (int v: d[u]) if (v != p && !dead[v])
ans += get_size(u, v);
return ans;
}
int find_centroid(int S, int p, int u, int ma = 0) {
numchild[u] = 1;
for (int v: d[u]) if (v != p && !dead[v]) {
int get = find_centroid(S, u, v);
if (get != -1) return get;
numchild[u] += numchild[v];
ma = max(ma, numchild[v]);
}
ma = max(ma, S - numchild[u]);
return ma <= S/2 ? u: -1;
}
void FIND_CENTROID() {
queue <int> q; q.push(1);
while (q.size()) {
int u = q.front(); q.pop();
dead[u = find_centroid(get_size(0, u), 0, u)] = true;
centroid.push_back(u);
for (int v: d[u]) if (!dead[v]) q.push(v);
}
}
vector <int> save[N];
void dfs(int p, int u, int vi) {
for (int v: d[u]) if (v != p && !dead[v]) {
h[v] = h[u] + 1;
H[v] = (H[u]*base + s[v]) % MOD;
rH[v] = (rH[u] + pw[h[v]]*s[v]) % MOD;
up[0][v] = u;
for (int i = 1; (1 << i) <= h[v]; i ++)
up[i][v] = up[i - 1][up[i - 1][v]];
save[vi == 0 ? v : vi].push_back(v);
dfs(u, v, vi == 0 ? v : vi);
}
}
int kanc(int k, int u) {
int x = u;
for (int i = 19; i >= 0; i --)
if (k & 1 << i) u = up[i][u];
return u;
}
ll get(int u, int v) {return (H[v] - H[u] * pw[h[v] - h[u]] + MOD * MOD) % MOD;}
bool solve_len(int len, int u) {
// return true;
if (len <= 1) return true;
H[u] = s[u]; rH[u] = s[u]; h[u] = 0;
dfs(u, u, 0);
unordered_set <int> st, st2; st.insert(0); st2.insert(0);
// cout << "--------- " << u << " ----------\n";
for (int vi: d[u]) if (!dead[vi]) {
for (int v: save[vi]) {
// cout << v << ' ';
int mis = len - h[v] - 1; if (mis < 0) continue;
// cout << u << ' ' << v << ' ' << get(u, v) << '\n';
if (mis >= h[v]) {
if (st2.count(get(u, v))) return true;
} else {
int anc = kanc(mis, v);
if (H[anc] == rH[anc] && st.count(get(anc, v))) return true;
}
}
// cout << '\n';
for (int v: save[vi]) {
int mis = len - h[v] - 1; if (mis < 0) continue;
if (mis > h[v]) st.insert(get(u, v)); else {
int anc = kanc(mis, v);
if (H[anc] == rH[anc]) st2.insert(get(anc, v));
}
}
}
return false;
}
int solve(int len) {
for (int i = 1; i <= n; i ++) dead[i] = false;
for (int u: centroid) {
int tmp = solve_len(len, u);
dead[u] = true;
for (int v: d[u]) save[v].clear();
if (tmp) return true;
}
return false;
}
int bs(int x) {
int l = 0, r = n/2 + 1, ans = x;
while (l <= r) {
int mid = l + r >> 1;
// cout << mid*2 + x << '\n';
if (solve(2*mid + x))
ans = mid * 2 + x, l = mid + 1;
else
r = mid - 1;
}
return ans;
}
ll SOLVE_CENTROID() {
return max(bs(0), bs(1));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
// #endif
cin >> n >> SS;
// s = ' ' + s;
for (int i = 1; i <= n; i ++)
s[i] = SS[i - 1] - 'a' + 1;
pw[0] = 1;
for (int i = 1; i < N; i ++)
pw[i] = pw[i - 1]*base % MOD;
for (int i = 1, u, v; i < n; i ++) {
cin >> u >> v;
d[u].push_back(v);
d[v].push_back(u);
}
FIND_CENTROID();
cout << SOLVE_CENTROID();// << ' ' << 1;
return 0;
}
/** /\_/\
(= ._.)
/ >🍵 \>🍮
________________________
/ Brainstorming section /
/=======================/
---
===
g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 somerandomthings.cpp -o somerandomthings.exe
12780
===
**/
// Before submit: spot the visible bug by reading the code.
