#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a>N; string S; cin>>S; int M=S.size(); vector>> g(N); rep(i,N-1){ int a,b; char c; cin>>a>>b>>c; a--;b--; int d=c-'a'; g[a].push_back(mkp(b,d)); g[b].push_back(mkp(a,d)); } vector> last(M+1,vector(26,-1)); for(int i=0;i> Rlast(M+1,vector(26,-1)); for(int i=0;i> last) -> vector> { vector> dp(N,vector (M+1,0)); auto dfs = [&](auto &&dfs,int now,int par)->void{ for(auto [nex,d]:g[now]){ if(nex==par) continue; dfs(dfs,nex,now); for(int k=0;k<=M;k++) chmax(dp[now][k],dp[nex][k]); for(int k=0;k<=M;k++){ int lt=last[k][d]; if(lt==-1) continue; chmax(dp[now][k],dp[nex][lt]+1); } } for(int k=0;k> sp=solve(last); reverse(all(S)); vector> tp=solve(Rlast); auto calc_ans = [&](auto &&calc_ans,int now,int par)->int{ vector>> ss(M+1),tt(M+1); rep(i,M+1){ ss[i].push_back(mkp(0,-1)); tt[i].push_back(mkp(0,-2)); } for(auto [nex,d]:g[now]){ if(nex==par) continue; calc_ans(calc_ans,nex,now); for(int k=0;k<=M;k++){ int slt=last[k][d]; int tlt=Rlast[k][d]; int sv=sp[nex][k],tv=tp[nex][k]; if(slt!=-1) chmax(sv,sp[nex][slt]+1); if(tlt!=-1) chmax(tv,tp[nex][tlt]+1); ss[k].push_back(mkp(sv,nex)); tt[k].push_back(mkp(tv,nex)); } } rep(i,M+1){ sort(all(ss[i])); reverse(all(ss[i])); sort(all(tt[i])); reverse(all(tt[i])); } int res=0; for(int k=0;k<=M;k++){ auto [f,ft]=ss[k][0]; auto [s,st]=tt[M-k][0]; if(ft==st){ if(tt[M-k].size()>=2) chmax(res,f+tt[M-k][1].first); if(ss[k].size()>=2) chmax(res,s+ss[k][1].first); }else{ chmax(res,f+s); } } return res; }; int ans=calc_ans(calc_ans,0,-1); cout<