#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef int64_t ll; typedef std::pair Pii; typedef std::pair Pll; typedef std::pair Pdd; #define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++) #define all(_l) _l.begin(), _l.end() #define rall(_l) _l.rbegin(), _l.rend() #define MM << " " << template using MaxHeap = std::priority_queue<_T>; template using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>; template inline bool chmax(_T &_l, const _T _b) { if (_l < _b) { _l = _b; return true; } return false; } template inline bool chmin(_T &_l, const _T _b) { if (_l > _b) { _l = _b; return true; } return false; } template void vdeb(const std::vector<_T> &bb) { for (unsigned int i = 0;i < bb.size();i++) { if (i == bb.size() - 1) std::cout << bb[i]; else std::cout << bb[i] << ' '; } std::cout << '\n'; } template void vdeb(const std::vector> &bb) { for (unsigned int i = 0;i < bb.size();i++) { // std::cout << i << ' '; vdeb(bb[i]); } std::cout << '\n'; } using namespace std; int N; string s; struct Edge { int to; char c; Edge() {} Edge(int _to, char _c) : to(_to),c(_c) {} }; struct DP { int n; vector dp; // DP() {} DP(int _n = s.size()) : n(_n), dp(n) {} DP addroot(char c) { DP ret(*this); rip(i,n,0) { if(i) ret.dp[i] = max(max(ret.dp[i-1], dp[i]), dp[i-1] + ((s[i] == c) ? 1 : 0)); else ret.dp[i] = (s[i] == c) ? 1 : 0; } return ret; } DP& operator+=(const DP &other) { rip(i,n,0) chmax(dp[i], other.dp[i]); return *this; } DP operator+(const DP &other) { DP ret(*this); rip(i,n,0) chmax(ret.dp[i], other.dp[i]); return ret; } }; void dfs1(vector> &da, vector &dp, int pare = -1, int child = 0) { for(int i = 0; i < int(da[child].size()); i++){ if(da[child][i].to == pare) continue; dfs1(da, dp, child, da[child][i].to); dp[child] += dp[da[child][i].to].addroot(da[child][i].c); } } void dfs2(vector> &da, vector &ans, const DP &dp = DP(), int pare = -1, int child = 0){ if(pare != -1) ans[child] += dp; int size = da[child].size(); vector dpL(size+1) ,dpR(size+1); for(int i = 0;i < size; i++){ int next = da[child][i].to; dpL[i+1] = dpL[i]; if(next == pare) dpL[i+1] += dp; else dpL[i+1] += ans[next].addroot(da[child][i].c); } for(int i = size; i > 0; i--){ int next = da[child][i-1].to; dpR[i-1] = dpR[i]; if(next == pare) dpR[i-1] += dp; else dpR[i-1] += ans[next].addroot(da[child][i-1].c); } for(int i = 0;i < size;i++){ int next = da[child][i].to; if(next == pare) continue; dfs2(da, ans, (dpL[i] + dpR[i+1]).addroot(da[child][i].c), child, next); } } void rooting(vector> &da, vector &dp) { dfs1(da, dp); dfs2(da, dp); } int main() { cin >> N; cin >> s; vector> da(N, vector(0)); rip(i,N-1,0) { int x, y; cin >> x >> y; char c; cin >> c; --x; --y; da[y].push_back({x, c}); da[x].push_back({y, c}); } vector dp(N, s.size()); rooting(da, dp); int ans = 0; rip(i,N,0) { chmax(ans, dp[i].dp.back()); } cout << ans << endl; }