#include using namespace std; #define rep(i, n) for(int i = 0; i < n; i++) #define rep2(i, x, n) for(int i = x; i <= n; i++) #define rep3(i, x, n) for(int i = x; i >= n; i--) #define each(e, v) for(auto &e: v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; const int MOD = 1000000007; //const int MOD = 998244353; const int inf = (1<<30)-1; const ll INF = (1LL<<60)-1; template bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;}; template bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;}; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; vector S(2); int N, M; vector>> dp(2, vector>(2000, vector(2001, 0))); int ans = 0; template struct Weighted_Graph{ struct edge{ int to; T cost; int id; edge(int to, T cost, int id) : to(to), cost(cost), id(id) {} }; vector> es; const T INF_T; const int n; int m; Weighted_Graph(int n) : es(n), INF_T(numeric_limits::max()/2), n(n), m(0) {} void add_edge(int from, int to, T cost){ es[from].emplace_back(to, cost, m); if(!directed) es[to].emplace_back(from, cost, m); m++; } void dfs(int now, int pre = -1){ each(e, es[now]){ if(e.to != pre) dfs(e.to, now); } vector> L(M+1), R(M+1), C(M+1); rep(t, 2){ rep2(i, 0, M){ each(e, es[now]){ if(e.to == pre) continue; int tmp = dp[t][e.to][i]; if(i > 0 && S[t][M-i] == e.cost){ chmax(tmp, dp[t][e.to][i-1]+1); } if(t == 0) C[i].eb(tmp); else L[i].eb(tmp), R[i].eb(tmp); chmax(dp[t][now][i], tmp); } if(i > 0) chmax(dp[t][now][i], dp[t][now][i-1]); } } int K = sz(L[0]); rep2(i, 0, M){ rep2(j, 1, K-1){ chmax(L[i][j], L[i][j-1]); } rep3(j, K-2, 0){ chmax(R[i][j], R[i][j+1]); } } chmax(ans, dp[0][now][M]), chmax(ans, dp[1][now][M]); rep2(i, 0, M){ rep(j, K){ int x = 0; if(j-1 >= 0) chmax(x, L[i][j-1]); if(j+1 < K) chmax(x, R[i][j+1]); chmax(ans, C[M-i][j]+x); } } } void solve(){ dfs(0); cout << ans << '\n'; /* rep(i, N){ rep(j, M+1){ cout << dp[0][i][j] << ' '; } cout << '\n'; } */ } }; int main(){ cin >> N >> S[0]; S[1] = S[0]; reverse(all(S[1])); M = sz(S[0]); Weighted_Graph G(N); rep(i, N-1){ int u, v; char c; cin >> u >> v >> c; u--, v--; G.add_edge(u, v, c); } G.solve(); }