#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast", "fast-math", "unroll-loops")
//#pragma GCC target ("avx2", "popcnt")
#ifdef LOCAL_
#include <debug.h>
#else
#define debug
#endif // LOCAL
using namespace std;
template <int M>
struct Hash1MOD
{
typedef Hash1MOD<M> Type;
unsigned long long x;
Hash1MOD(unsigned long long _x = 0) : x(_x % M) {}
inline Type operator+(const Type &oth) const {return x + oth.x;}
inline Type operator-(const Type &oth) const {return x - oth.x + M;}
inline Type operator*(const Type &oth) const {return x * oth.x;}
inline Type &operator+=(const Type &oth) {return *this = *this + oth;}
inline Type &operator-=(const Type &oth) {return *this = *this - oth;}
inline Type &operator*=(const Type &oth) {return *this = *this * oth;}
inline bool operator==(const Type &oth) const {return x == oth.x;}
inline bool operator!=(const Type &oth) const {return !(*this == oth);}
};
template <int M1, int M2>
struct Hash2MOD
{
typedef Hash2MOD<M1,M2> Type;
Hash1MOD<M1> x1;
Hash1MOD<M2> x2;
Hash2MOD(unsigned long long _x = 0) : x1(_x), x2(_x) {}
Hash2MOD(const Hash1MOD<M1> &_x1, const Hash1MOD<M2> &_x2) : x1(_x1), x2(_x2) {}
inline Type operator+(const Type &oth) const {return Type(x1 + oth.x1, x2 + oth.x2);}
inline Type operator-(const Type &oth) const {return Type(x1 - oth.x1, x2 - oth.x2);}
inline Type operator*(const Type &oth) const {return Type(x1 * oth.x1, x2 * oth.x2);}
inline Type &operator+=(const Type &oth) {x1 += oth.x1; x2 += oth.x2; return *this;}
inline Type &operator-=(const Type &oth) {x1 -= oth.x1; x2 -= oth.x2; return *this;}
inline Type &operator*=(const Type &oth) {x1 *= oth.x1; x2 *= oth.x2; return *this;}
inline bool operator==(const Type &oth) const {return x1 == oth.x1 && x2 == oth.x2;}
inline bool operator!=(const Type &oth) const {return !(*this == oth);}
};
typedef unsigned long long HashType;
const HashType BASE(10037);
HashType baseexp[50005];
HashType h1[50005], h2[50005];
vector<int> v[50005];
vector<int> cv[50005];
string str;
int depth[50005];
int down[50005];
int cdown[50005];
int up[20][50005];
int color[50005];
void dfs(int node)
{
for(auto &i : v[node])
if(!depth[i])
{
depth[i] = depth[node] + 1;
dfs(i);
}
}
void pushNodes(int node, int except, vector<int> &nlist)
{
nlist.push_back(node);
for(auto &i : v[node])
if(i != except)
pushNodes(i, node, nlist);
}
int badSon(int node, int N)
{
for(auto &i : v[node])
if(down[i] > N/2)
return i;
return 0;
}
void dfsColor(int node, int col)
{
color[node] = col;
for(auto &son : v[node])
if(color[son] == 0)
dfsColor(son, col);
}
bool solve(vector<int> nlist, int root, int len)
{
if(len == 1) return true;
if(nlist.size() == 1) return false;
int node;
while(node = badSon(root, nlist.size()))
{
down[root] -= down[node];
down[node] = nlist.size();
root = node;
}
for(auto &i : nlist) depth[i] = 0;
depth[root] = 1;
dfs(root);
int res = 0;
sort(nlist.begin(), nlist.end(), [](const int &x, const int &y){return depth[x] < depth[y];});
for(auto &i : nlist)
for(int j=0; j<17; ++j)
up[j][i] = 0;
for(auto &i : nlist)
{
if(i == root)
{
h1[i] = h2[i] = str[i];
continue;
}
for(auto &j : v[i])
if(depth[j] < depth[i])
{
up[0][i] = j;
h1[i] = h1[j] * BASE + str[i];
h2[i] = h2[j] + baseexp[depth[j]] * str[i];
break;
}
}
// debug("root = %\n", root);
// for(auto &node : nlist)
// debug("node = %, str[node] = %, h1 = %, h2 = %\n", node, str[node], h1[node], h2[node]);
for(int i=1; i<17; ++i)
for(auto &j : nlist)
up[i][j] = up[i-1][up[i-1][j]];
for(auto &node : nlist)
color[node] = 0;
color[root] = -1;
for(int i=0; i<v[root].size(); ++i)
dfsColor(v[root][i], i+1);
vector<unordered_map<HashType, int>> fr(v[root].size() + 1);
for(auto &node : nlist)
{
// debug("node = %, color = %\n", node, color[node]);
if(color[node] != -1)
++fr[color[node]][h1[node]];
++fr[0][h1[node]];
}
for(auto &node : nlist)
{
int kth = node, by = len - depth[node];
for(int bit = 0; bit < 17; ++bit)
if(by & (1<<bit))
kth = up[bit][kth];
// debug("node = %, by = %, kth = %\n", node, by, kth);
if(kth == 0) continue;
HashType myHash = h1[node] - h1[up[0][kth]] * baseexp[by+1];
if(node == root) continue;
if(h1[kth] != h2[kth]) continue;
// debug("myHash = %, color[node] = %, fr1 = %, fr2 = %\n", myHash, color[node], fr[color[node]][myHash], fr[0][myHash]);
if(fr[color[node]][myHash] != fr[0][myHash])
{
// cout<<node<<' '<<root<<'\n';
return true;
}
}
for(auto &son : v[root])
{
vector<int> nodes;
pushNodes(son, root, nodes);
v[son].erase(lower_bound(v[son].begin(), v[son].end(), root));
if(solve(nodes, son, len))
return true;
}
return false;
}
void reset(int n)
{
for(int i=1; i<=n; ++i)
v[i] = cv[i], down[i] = cdown[i];
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
baseexp[0] = 1;
for(int i=1; i<50005; ++i)
baseexp[i] = baseexp[i-1] * BASE;
int n; cin>>n;
if(n == 1)
{
cout<<'1';
return 0;
}
else if(n == 2)
{
cin>>str;
cout<<(str[0] == str[1] ? 2 : 1);
return 0;
}
cin>>str;
str = "#" + str;
for(int i=n-1; i>=1; --i)
{
int a,b; cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
// v[n].push_back(a);
// v[n].push_back(b);
// str.push_back('*');
}
// for(int i=n; i>=1; --i)
// if(v[i].size() == 1)
// {
// v[++n].push_back(i);
// v[i].push_back(n);
// str.push_back('*');
// }
depth[1] = 1;
dfs(1);
for(int i=1; i<=n; ++i)
sort(v[i].begin(), v[i].end());
vector<int> nlist(n);
for(int i=1; i<=n; ++i)
nlist[i-1] = i;
sort(nlist.begin(), nlist.end(), [](const int &x, const int &y){return depth[x] > depth[y];});
for(auto &node : nlist)
{
down[node] = 1;
for(auto &son : v[node])
if(depth[son] > depth[node])
down[node] += down[son];
}
for(int i=1; i<=n; ++i)
cv[i] = v[i], cdown[i] = down[i];
int ans = -1;
int st = 0, dr = (n+1)/2, mij;
while(st <= dr)
{
mij = (st+dr>>1);
reset(n);
if(!solve(nlist, 1, mij*2+1)) dr = mij-1;
else st = mij+1;
}
ans = max(ans, dr*2+1);
st = 0, dr = (n+1)/2, mij;
while(st <= dr)
{
mij = (st+dr>>1);
reset(n);
if(!solve(nlist, 1, mij*2)) dr = mij-1;
else st = mij+1;
}
ans = max(ans, dr*2);
cout<<ans;
return 0;
}
