Lampice

#include <bits/stdc++.h>

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

typedef pair<int, int> Hash;
const int mod1 = 1e9+7, mod2 = 1e9+9, b1 = 31, b2 = 37;

Hash operator+(Hash lhs, const Hash &rhs)
{
    lhs.F += rhs.F;
    if (lhs.F >= mod1) lhs.F -= mod1;
    lhs.S += rhs.S;
    if (lhs.S >= mod2) lhs.S -= mod2;
    return lhs;
}

Hash operator-(Hash lhs, const Hash &rhs)
{
    lhs.F += mod1 - rhs.F;
    if (lhs.F >= mod1) lhs.F -= mod1;
    lhs.S += mod2 - rhs.S;
    if (lhs.S >= mod2) lhs.S -= mod2;
    return lhs;
}

Hash operator*(Hash lhs, const Hash &rhs)
{
    lhs.F = (ll)lhs.F * rhs.F % mod1;
    lhs.S = (ll)lhs.S * rhs.S % mod2;
    return lhs;
}

const int N = 5e4 + 2;
Hash B[N];

inline ll Get(const Hash &h)
{
    return ((ll)h.F) << 32 | h.S;
}

struct centroid_decomposition
{
    int n;
    string ids;
    vector<bool> del;
    vector<vector<int>> adj;
    vector<int> size, parent;
    vector<vector<pair<pair<Hash, Hash>, int>>> hs;

    centroid_decomposition(int n) : n(n), del(n), adj(n), size(n), parent(n) {};

    void add_edge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int centroid(int u)
    {
        vector<int> seen = {u};
        parent[u] = -1;

        for (size_t i = 0; i < seen.size(); ++i)
        {
            u = seen[i];
            for (int v : adj[u])
                if (!del[v] && v != parent[u])
                    parent[v] = u, seen.push_back(v);
        }

        for (int sz = seen.size(), i = sz - 1, mx = 0; i >= 0; --i, mx = 0)
        {
            size[u = seen[i]] = 1;
            for (int v : adj[u])
                if (!del[v] && v != parent[u])
                    size[u] += size[v], mx = max(mx, size[v]);
            if (max(sz - size[u], mx) <= sz / 2)
                return u;
        }

        return -1;
    }

    void dfs(int u, int p, int d, Hash up, Hash down, vector<pair<pair<Hash, Hash>, int>> &h)
    {
        up = up * B[1] + Hash((ids[u] - 'a'), (ids[u] - 'a'));
        down = down + Hash((ids[u] - 'a'), (ids[u] - 'a')) * B[d];
        h.push_back({ { up, down }, d+1 });
        for (int v : adj[u])
            if (!del[v] && v != p)
                dfs(v, u, d + 1, up, down, h);
    }

    bool check(int c, int len)
    {
        set<pair<ll, int>> mp;
        for (auto &h : hs)
        {
            for (auto &i : h)
                if (len-i.S >= 0 && mp.find({ Get(i.F.F - i.F.S * B[len-i.S]), len-i.S }) != mp.end())
                    return true;

            for (auto &i : h)
            {
                auto up = i.F.F;
                auto down = i.F.S;
                down = down * B[1] + Hash((ids[c] - 'a'), (ids[c] - 'a'));
                up = up + Hash((ids[c] - 'a'), (ids[c] - 'a')) * B[i.S];
                if (up == down && i.S + 1 >= len) return true;
                if (len-i.S-1 >= 0)
                    mp.insert({ Get(up - down * B[len - i.S - 1]), i.S + 1 });
            }
        }
        return false;
    }

    int rootify(int r)
    {
        int c = centroid(r);
        assert(c != -1);
        del[c] = true;

        hs.clear();
        for (int v : adj[c])
            if (!del[v])
            {
                hs.emplace_back();
                dfs(v, c, 0, Hash(0, 0), Hash(0, 0), hs.back());
            }

        int lo = 2, hi = n;
        while (hi - lo > 3)
        {
            int md = (lo + hi + 1) >> 1;
            if (check(c, md) || check(c, md+1))
                lo = md;
            else
                hi = md - 1;
        }

        int ret = 1;
        for (; hi >= lo; --hi)
            if (check(c, hi))
            {
                ret = hi;
                break;
            }

        for (int v : adj[c])
            if (!del[v])
                ret = max(ret, rootify(v));

        return ret;
    }
};

int main()
{
    #ifdef DGC
        freopen("a.in", "r", stdin);
        //freopen("b.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;
    B[0] = make_pair(1, 1);
    for (int i = 1; i <= n; ++i)
        B[i] = B[i-1] * Hash(b1, b2);

    centroid_decomposition cd(n);
    cin >> cd.ids;
    for (auto &i : cd.ids) i += 1;
    for (int u, v, i = 1; i < n; ++i)
    {
        cin >> u >> v;
        --u, --v;
        cd.add_edge(u, v);
    }

    cout << cd.rootify(0) << "\n";

    return 0;
}