#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;
bool M1;
#define MAXN 50505
int numNode;
string nodeChar;
int intChar[MAXN];
vector<int> g[MAXN];
bool block[MAXN];
int sizeTree[MAXN];
int parent[MAXN];
const int base = 256;
const int MOD = 1e9 + 19972207;
int p[MAXN];
int ip[MAXN];
int curHash[MAXN];
int revCurHash[MAXN];
///++++++++++++++++++++++++++++++++++++++///
int mul(int a, int b){
return (a * b) % MOD;
}
int Pow(int a, int b) {
if (b == 0) return 1;
int tmp = Pow(a, b >> 1);
return (b & 1 ? mul(a, mul(tmp, tmp)) : mul(tmp, tmp));
}
int Div(int a, int b) {
return mul(a, ip[b]);
}
int add(int a, int b) {
return ((a + b) % MOD + MOD) % MOD;
}
void calc(int u, int p) {
sizeTree[u] = 1;
for (int &v : g[u]) {
if (block[v] || v == p) continue;
calc(v, u);
sizeTree[u] += sizeTree[v];
}
}
int FindCentroid(int u, int p, int SZ) {
for (int &v : g[u]) {
if (block[v] || v == p) continue;
if (sizeTree[v] > SZ) return FindCentroid(v, u, SZ);
}
return u;
}
void decompose(int u, int par) {
calc(u, 0);
int c = FindCentroid(u, 0, sizeTree[u] / 2);
parent[c] = par;
block[c] = 1;
for (int &v : g[u]) {
if (block[v]) continue;
decompose(v, c);
}
}
bool pushDown(int u, int par, int depth, int revLength, int aimLength, int blocked, unordered_map<int, bool> &marked, vector<int> &vecAdd) {
curHash[depth] = (curHash[depth - 1] + (intChar[u] * p[depth - 1])) % MOD;
revCurHash[depth] = (revCurHash[depth - 1] + (intChar[u] * p[revLength])) % MOD;
if (depth >= aimLength) {
if (depth == aimLength) {
int revHash = Div(revCurHash[depth], revLength);
if (revHash == curHash[depth]) return true;
} else {
return false;
}
} else {
int addHash = add(curHash[depth], -curHash[1]);
addHash = Div(addHash, 1);
vecAdd.push_back(addHash);
int leftLength = aimLength - depth;
if (depth >= leftLength) {
{
int Hash = curHash[depth - leftLength];
int revHash = Div(revCurHash[depth - leftLength], revLength + leftLength);
if (Hash == revHash) {
int nowHash = add(curHash[depth], -curHash[depth - leftLength]);
nowHash = Div(nowHash, depth - leftLength + 1);
if (marked[nowHash]) return true;
}
}
}
}
for (int &v : g[u]) {
if (v == par || v == blocked) continue;
bool good = pushDown(v, u, depth + 1, revLength - 1, aimLength, blocked, marked, vecAdd);
if (good) return true;
}
return false;
}
bool process(int midNode, int curLength) {
unordered_map<int, bool> marked;
curHash[1] = (intChar[midNode] * p[0]) % MOD;
revCurHash[1] = (intChar[midNode] * p[numNode]) % MOD;
for (int &curNode : g[midNode]) {
if (curNode == parent[midNode]) continue;
vector<int> vecAdd;
bool good = pushDown(curNode, midNode, 2, numNode - 1, curLength, parent[midNode], marked, vecAdd);
if (good) return true;
for (int &nowHash : vecAdd) marked[nowHash] = true;
vecAdd.clear();
}
return false;
}
bool lengthPalin(int curLength) {
FOR(midNode, 1, numNode) {
bool found = process(midNode, curLength);
if (found) return true;
}
return false;
}
void solve() {
cin >> numNode;
cin >> nodeChar;
p[0] = 1;
FOR(i, 1, numNode) p[i] = (p[i - 1] * base) % MOD;
FOR(i, 0, numNode) ip[i] = Pow(p[i], MOD - 2);
FOR(i, 1, numNode) intChar[i] = nodeChar[i - 1] - 'a' + 1;
FOR(i, 1, numNode - 1) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
decompose(1, 0);
int ans = 1;
{
int lo = 0, hi = numNode / 2;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (lengthPalin(2 * mid)) {
ans = max(ans, 2 * mid);
lo = mid + 1;
} else hi = mid - 1;
}
}
{
int lo = 0, hi = numNode / 2;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (lengthPalin(2 * mid + 1)) {
ans = max(ans, 2 * mid + 1);
lo = mid + 1;
} else hi = mid - 1;
}
}
cout << ans;
}
///++++++++++++++++++++++++++++++++++++++///
#define task "COCI19_lampice"
int32_t main() {
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
bool M2;
cerr << "++++++++++++++++++++++++++++\n";
cerr << "Time: " << clock() << " ms" << '\n';
cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << " MB" << '\n';
cerr << "++++++++++++++++++++++++++++\n";
return 0;
}
