#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;
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
using namespace std;
using namespace __gnu_pbds;
const int base = 311;
int n;
vector<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 centroidDecomposition
{
int sz[maxn];
bool del[maxn];
void init()
{
memset(del, 0, (n + 1) * sizeof(bool));
}
void dfs(int u, int p)
{
sz[u] = 1;
for (auto &v : edges[u])
{
if (v == p || del[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int p, int total)
{
for (auto &v : edges[u])
{
if (v == p || del[v]) continue;
if (sz[v] > (total >> 1))
return findCentroid(v, u, total);
}
return u;
}
bool dfs_update(int u, int p, int depth, int len)
{
hs.push(a[u]);
if (depth * 2 >= len && hs.IsPalin(2 * depth - len)) //duong di qua goc tu 2 dinh con cach goc 1 khoang depth
m[hs.get(len - depth)] = 1;
if (depth == len && hs.IsPalin(len))
return 1;
for (auto &v : edges[u])
{
if (v == p || del[v]) continue;
if (dfs_update(v, u, depth + 1, len)) return 1;
}
hs.pop();
return 0;
}
bool dfs_search(int u, int p, int depth, int len)
{
hs.push(a[u]);
if (depth * 2 <= len && m[hs.get(depth)]) //chi 1 nhanh
return 1;
if (depth == len && hs.IsPalin(len))
return 1;
for (auto &v : edges[u])
{
if (v == p || del[v]) continue;
if (dfs_search(v, u, depth + 1, len)) return 1;
}
hs.pop();
return 0;
}
bool decompose(int u, int len)
{
dfs(u, -1);
int centroid = findCentroid(u, -1, sz[u]);
del[centroid] = 1;
for (int turn = 0; turn <= 1; ++turn)
{
m.clear();
for (auto &v : edges[centroid])
{
if (del[v]) continue;
hs.clear();
if (dfs_search(v, centroid, 1, len))
return 1;
hs.clear();
hs.push(a[centroid]);
if (dfs_update(v, centroid, 2, len))
return 1;
}
reverse(edges[centroid].begin() , edges[centroid].end());
}
for (auto &v : edges[centroid])
{
if (del[v]) continue;
if (decompose(v, len)) return 1;
}
return 0;
}
} 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;
// file("txt");
// int t ; cin >> t ; while (t--)
solve();
return 0;
}
