#include using namespace std; int main(){ int N; cin >> N; string S; cin >> S; int M = S.size(); vector>> E(N); for (int i = 0; i < N - 1; i++){ int u, v; char c; cin >> u >> v >> c; u--; v--; E[u].push_back(make_pair(c, v)); E[v].push_back(make_pair(c, u)); } vector p(N, -1); vector p2(N); vector> c(N); queue Q; Q.push(0); vector bfs; while (!Q.empty()){ int v = Q.front(); Q.pop(); bfs.push_back(v); for (auto P : E[v]){ int w = P.second; if (w != p[v]){ p[w] = v; p2[w] = P.first; c[v].push_back(w); Q.push(w); } } } reverse(bfs.begin(), bfs.end()); vector> dp1(N, vector(M + 1, 0)); for (int v : bfs){ for (int i = 0; i < M; i++){ dp1[v][i + 1] = max(dp1[v][i + 1], dp1[v][i]); } if (v != 0){ for (int i = 0; i <= M; i++){ dp1[p[v]][i] = max(dp1[p[v]][i], dp1[v][i]); } for (int i = 0; i < M; i++){ if (S[i] == p2[v]){ dp1[p[v]][i + 1] = max(dp1[p[v]][i + 1], dp1[v][i] + 1); } } } } vector> dp2(N, vector(M + 1, 0)); for (int v : bfs){ for (int i = M - 1; i >= 0; i--){ dp2[v][i] = max(dp2[v][i], dp2[v][i + 1]); } if (v != 0){ for (int i = M; i >= 0; i--){ dp2[p[v]][i] = max(dp2[p[v]][i], dp2[v][i]); } for (int i = M - 1; i >= 0; i--){ if (S[i] == p2[v]){ dp2[p[v]][i] = max(dp2[p[v]][i], dp2[v][i + 1] + 1); } } } } int ans = 0; for (int i = 0; i <= M; i++){ ans = max(ans, dp1[0][i]); ans = max(ans, dp2[0][i]); } for (int v : bfs){ vector mx1(M + 1, 0); vector mx2(M + 1, 0); for (int w : c[v]){ for (int i = 0; i <= M; i++){ ans = max(ans, mx1[i] + dp2[w][i]); mx1[i] = max(mx1[i], dp1[w][i]); ans = max(ans, mx2[i] + dp1[w][i]); mx2[i] = max(mx2[i], dp2[w][i]); } } } cout << ans << endl; }