結果

問題 No.1295 木と駒
ユーザー hashiryohashiryo
提出日時 2023-02-06 00:09:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 23,952 bytes
コンパイル時間 4,701 ms
コンパイル使用メモリ 285,276 KB
最終ジャッジ日時 2025-02-10 11:17:55
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on
template <class Int> constexpr inline Int mod_inv(Int a, Int mod) {
 static_assert(std::is_signed_v<Int>);
 Int x= 1, y= 0, b= mod;
 for (Int q= 0, z= 0, c= 0; b;) z= x, c= a, x= y, y= z - y * (q= a / b), a= b, b= c - b * q;
 return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;
}
namespace math_internal {
using namespace std;
using u8= uint8_t;
using u32= uint32_t;
using u64= uint64_t;
using i64= int64_t;
using u128= __uint128_t;
#define CE constexpr
#define IL inline
#define NORM \
 if (n >= mod) n-= mod; \
 return n
#define PLUS(U, M) \
 CE IL U plus(U l, U r) const { \
  if (l+= r; l >= M) l-= M; \
  return l; \
 }
#define DIFF(U, C, M) \
 CE IL U diff(U l, U r) const { \
  if (l-= r; l >> C) l+= M; \
  return l; \
 }
#define SGN(U) \
 static CE IL U set(U n) { return n; } \
 static CE IL U get(U n) { return n; } \
 static CE IL U norm(U n) { return n; }
template <class u_t, class du_t, u8 B, u8 A> struct MP_Mo {
 const u_t mod;
 CE MP_Mo(): mod(0), iv(0), r2(0) {}
 CE MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {}
 CE IL u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); }
 PLUS(u_t, mod << 1)
 DIFF(u_t, A, mod << 1)
 CE IL u_t set(u_t n) const { return mul(n, r2); }
 CE IL u_t get(u_t n) const {
  n= reduce(n);
  NORM;
 }
 CE IL u_t norm(u_t n) const { NORM; }
private:
 const u_t iv, r2;
 static CE u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; }
 CE IL u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); }
};
struct MP_Na {
 const u32 mod;
 CE MP_Na(): mod(0){};
 CE MP_Na(u32 m): mod(m) {}
 CE IL u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32)
};
struct MP_Br {  // mod < 2^31
 const u32 mod;
 CE MP_Br(): mod(0), s(0), x(0) {}
 CE MP_Br(u32 m): mod(m), s(__lg(m - 1) + 64), x(((u128(1) << s) + m - 1) / m) {}
 CE IL u32 mul(u32 l, u32 r) const { return rem(u64(l) * r); }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) private: const u8 s;
 const u64 x;
 CE IL u64 quo(u64 n) const { return (u128(x) * n) >> s; }
 CE IL u32 rem(u64 n) const { return n - quo(n) * mod; }
};
struct MP_Br2 {  // 2^20 < mod <= 2^41
 const u64 mod;
 CE MP_Br2(): mod(0), x(0) {}
 CE MP_Br2(u64 m): mod(m), x((u128(1) << 84) / m) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); }
 PLUS(u64, mod << 1)
 DIFF(u64, 63, mod << 1)
 static CE IL u64 set(u64 n) { return n; }
 CE IL u64 get(u64 n) const { NORM; }
 CE IL u64 norm(u64 n) const { NORM; }
private:
 const u64 x;
 CE IL u128 quo(const u128 &n) const { return (n * x) >> 84; }
 CE IL u64 rem(const u128 &n) const { return n - quo(n) * mod; }
};
struct MP_D2B1 {
 const u64 mod;
 CE MP_D2B1(): mod(0), s(0), d(0), v(0) {}
 CE MP_D2B1(u64 m): mod(m), s(__builtin_clzll(m)), d(m << s), v(u128(-1) / d) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; }
 PLUS(u64, mod) DIFF(u64, 63, mod) SGN(u64) private: CE IL u64 rem(const u128 &u) const {
  u128 q= (u >> 64) * v + u;
  u64 r= u64(u) - (q >> 64) * d - d;
  if (r > u64(q)) r+= d;
  if (r >= d) r-= d;
  return r;
 }
 const u8 s;
 const u64 d, v;
};
template <class u_t, class MP> CE u_t pow(u_t x, u64 k, const MP &md) {
 for (u_t ret= md.set(1);; x= md.mul(x, x))
  if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret;
}
#undef NORM
#undef PLUS
#undef DIFF
#undef SGN
#undef CE
}
namespace math_internal {
#define CE constexpr
struct m_b {};
struct s_b: m_b {};
template <class mod_t> CE bool is_modint_v= is_base_of_v<m_b, mod_t>;
template <class mod_t> CE bool is_staticmodint_v= is_base_of_v<s_b, mod_t>;
template <class MP, u64 MOD> struct SB: s_b {
protected:
 static CE MP md= MP(MOD);
};
template <class Int, class U, class B> struct MInt: public B {
 using Uint= U;
 static CE inline auto mod() { return B::md.mod; }
 CE MInt(): x(0) {}
 CE MInt(const MInt &r): x(r.x) {}
 template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr> CE MInt(T v): x(B::md.set(v.val() % B::md.mod)) {}
 template <class T, enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr> CE MInt(T n): x(B::md.set((n < 0 ? B::md.mod - (-n) % B::md.mod : n % B::md.mod))) {}
 CE MInt operator-() const { return MInt() - *this; }
#define FUNC(name, op) \
 CE MInt name const { \
  MInt ret; \
  ret.x= op; \
  return ret; \
 }
 FUNC(operator+(const MInt &r), B::md.plus(x, r.x))
 FUNC(operator-(const MInt &r), B::md.diff(x, r.x))
 FUNC(operator*(const MInt &r), B::md.mul(x, r.x))
 FUNC(pow(u64 k), math_internal::pow(x, k, B::md))
#undef FUNC
 CE MInt operator/(const MInt &r) const { return *this * r.inv(); }
 CE MInt &operator+=(const MInt &r) { return *this= *this + r; }
 CE MInt &operator-=(const MInt &r) { return *this= *this - r; }
 CE MInt &operator*=(const MInt &r) { return *this= *this * r; }
 CE MInt &operator/=(const MInt &r) { return *this= *this / r; }
 CE bool operator==(const MInt &r) const { return B::md.norm(x) == B::md.norm(r.x); }
 CE bool operator!=(const MInt &r) const { return !(*this == r); }
 CE bool operator<(const MInt &r) const { return B::md.norm(x) < B::md.norm(r.x); }
 CE inline MInt inv() const { return mod_inv<Int>(val(), B::md.mod); }
 CE inline Uint val() const { return B::md.get(x); }
 friend ostream &operator<<(ostream &os, const MInt &r) { return os << r.val(); }
 friend istream &operator>>(istream &is, MInt &r) {
  i64 v;
  return is >> v, r= MInt(v), is;
 }
private:
 Uint x;
};
template <u64 MOD> using ModInt= conditional_t < (MOD < (1 << 30)) & MOD, MInt<int, u32, SB<MP_Mo<u32, u64, 32, 31>, MOD>>, conditional_t < (MOD < (1ull << 62)) & MOD, MInt<i64, u64, SB<MP_Mo<u64, u128, 64, 63>, MOD>>, conditional_t<MOD<(1u << 31), MInt<int, u32, SB<MP_Na, MOD>>, conditional_t<MOD<(1ull << 32), MInt<i64, u32, SB<MP_Na, MOD>>, conditional_t<MOD <= (1ull << 41), MInt<i64, u64, SB<MP_Br2, MOD>>, MInt<i64, u64, SB<MP_D2B1, MOD>>>>>>>;
#undef CE
}
using math_internal::ModInt, math_internal::is_modint_v, math_internal::is_staticmodint_v;
template <class mod_t, size_t LM> mod_t get_inv(int n) {
 static_assert(is_modint_v<mod_t>);
 static const auto m= mod_t::mod();
 static mod_t dat[LM];
 static int l= 1;
 if (l == 1) dat[l++]= 1;
 while (l <= n) dat[l++]= dat[m % l] * (m - m / l);
 return dat[n];
}
template <class Cost= void> class Tree {
 template <class D, class T> struct Edge_B {
  int to;
  T cost;
 };
 template <class D> struct Edge_B<D, void> { int to; };
 using Edge= Edge_B<void, Cost>;
 std::vector<std::vector<Edge>> adj;
 std::vector<int> P, PP, D, I, L, R;
public:
 Tree(int n): adj(n) {}
 template <class T= Cost, std::enable_if_t<std::is_same_v<T, void>, std::nullptr_t> = nullptr> void add_edge(int u, int v) { adj[u].emplace_back(Edge{v}), adj[v].emplace_back(Edge{u}); }
 template <class T, std::enable_if_t<std::is_convertible_v<T, Cost>, std::nullptr_t> = nullptr> void add_edge(int u, int v, T c) { adj[u].emplace_back(Edge{v, c}), adj[v].emplace_back(Edge{u, c}); }
 template <class T, class U, std::enable_if_t<std::conjunction_v<std::is_convertible<T, Cost>, std::is_convertible<U, Cost>>, std::nullptr_t> = nullptr> void add_edge(int u, int v, T c, U d) /* c:u->v, d:v->u */ { adj[u].emplace_back(Edge{v, c}), adj[v].emplace_back(Edge{u, d}); }
 const std::vector<Edge> &operator[](int v) const { return adj[v]; }
 void build(int root= 0) {
  const int n= adj.size();
  P.assign(n, -2), I.reserve(n), PP.resize(n), std::iota(PP.begin(), PP.end(), 0), D.assign(n, 0), L.assign(n, 0), R.assign(n, 0);
  auto f= [&, i= 0, v= 0](int r) mutable {
   for (P[r]=-1, I.push_back(r); i < (int)I.size(); ++i)
    for (const Edge &e: adj[v= I[i]])
     if (P[v] != e.to) I.push_back(e.to), P[e.to]= v;
  };
  f(root);
  for (int r= 0; r < n; ++r)
   if (P[r] == -2) f(r);
  std::vector<int> Z(n, 1), nx(n, -1);
  for (int i= n, v; i--;) {
   if (P[v= I[i]] == -1) continue;
   if (Z[P[v]]+= Z[v]; nx[P[v]] == -1) nx[P[v]]= v;
   if (Z[nx[P[v]]] < Z[v]) nx[P[v]]= v;
  }
  for (int v: I)
   if (nx[v] != -1) PP[nx[v]]= v;
  for (int v: I)
   if (P[v] != -1) PP[v]= PP[PP[v]], D[v]= D[P[v]] + 1;
  for(int i=0;i<n;++i) L[I[i]]=i;
  for (int v: I) {
   int ir= R[v]= L[v] + Z[v];
   for (const Edge &e: adj[v])
    if (int u=e.to;u != P[v] && u != nx[v]) L[u]= ir-= Z[u];
   if (nx[v] != -1) L[nx[v]]= L[v] + 1;
  }
  for (int i= 0; i < n; ++i) I[L[i]]= i;
 }
 int size() const { return adj.size(); }
 bool builded()const{return L.size()==adj.size();}
 int depth(int v) const { return assert(builded()),D[v]; }
 int to_seq(int v) const { return assert(builded()),L[v]; }
 int to_node(int i) const { return assert(builded()),I[i]; }
 int parent(int v) const { return assert(builded()),P[v]; }
 int root(int v) const {
  for (assert(builded()),v= PP[v];; v= PP[P[v]])
   if (P[v] == -1) return v;
 }
 bool connected(int u, int v) const {return root(u)==root(v);}
 int lca(int u, int v) const {
  for (assert(builded());; v= P[PP[v]]) {
   if (L[u] > L[v]) std::swap(u, v);
   if (PP[u] == PP[v]) return u;
  }
 }
 int la(int v, int k) const {
  assert(builded()),assert(k <= D[v]);
  for (int u;; k-= L[v] - L[u] + 1, v= P[u])
   if (L[v] - k >= L[u= PP[v]]) return I[L[v] - k];
 }
 int jump(int u, int v, int k) const {
  if (assert(builded());u == v) return -1;
  if (k == 1) return in_subtree(v, u) ? la(v, D[v] - D[u] - 1) : P[u];
  int w= lca(u, v), d_uw= D[u] - D[w], d_vw= D[v] - D[w];
  return k > d_uw + d_vw ? -1 : k <= d_uw ? la(u, k) : la(v, d_uw + d_vw - k);
 }
 int dist(int u, int v) const { return assert(builded()),depth(u) + depth(v) - depth(lca(u, v)) * 2; }
 bool in_subtree(int u, int v) /* u is in v */ const { return assert(builded()),L[v] <= L[u] && L[u] < R[v]; }
 int subtree_size(int v) const { return assert(builded()),R[v] - L[v]; }
 std::array<int, 2> subtree(int v) /* half-open interval */ const { return assert(builded()),std::array{L[v], R[v]}; }
 template <bool edge= 0> std::vector<std::array<int, 2>> path(int u, int v) /* sequence of closed intervals */ const {
  assert(builded());
  std::vector<std::array<int, 2>> up, down;
  while (PP[u] != PP[v]) {
   if (L[u] < L[v]) down.emplace_back(std::array{L[PP[v]], L[v]}), v= P[PP[v]];
   else up.emplace_back(std::array{L[u], L[PP[u]]}), u= P[PP[u]];
  }
  if (L[u] < L[v]) down.emplace_back(std::array{L[u] + edge, L[v]});
  else if (L[v] + edge <= L[u]) up.emplace_back(std::array{L[u], L[v] + edge});
  return up.insert(up.end(), down.rbegin(), down.rend()), up;
 }
};
template <class T, class C> class ReRootingData {
 Tree<C> &tree;
 std::vector<T> dp1, dp2, dp;
public:
ReRootingData(Tree<C> &t,std::vector<T>& d1,std::vector<T>& d2,std::vector<T>& d):tree(t),dp1(d1),dp2(d2),dp(d){}
 T operator[](int v)const { return dp[v]; }
 auto begin() const { return dp.begin(); }
 auto end() const { return dp.end(); }
 const T& get(int root, int v)const{
  return root==v?dp[v]:tree.in_subtree(root,v)? dp2[tree.jump(v,root,1)]:dp1[v];
 }
};
template <class T, class U, class C,  class F1, class F2, class F3>
ReRootingData<T,C> rerooting(Tree<C> &t, const F1 &f_ee, const F2 &f_ve, const F3 &f_ev, const U &unit){
  const int n= t.size();
  std::vector<T> dp1(n), dp2(n), dp(n);
  for (int i= n; i--;) {
   int v= t.to_node(i);
   U sum= unit;
   for (const auto &e: t[v])
    if (int u=e.to;u != t.parent(v)) sum= f_ee(sum, f_ve(dp1[u], v, e));
   dp1[v]= f_ev(sum, v);
  }
  for (int i= 0; i < n; ++i) {
   int v= t.to_node(i), deg= t[v].size();
   std::vector<U> f(deg + 1), b(deg + 1);
   for (int j= 0; j < deg; ++j) {
    const auto &e= t[v][j];
    int u= e.to;
    f[j + 1]= f_ve(u == t.parent(v) ? dp2[v] : dp1[u],v, e);
   }
   f[0]= b[deg]= unit;
   for (int j= deg; j--;) b[j]= f_ee(f[j + 1], b[j + 1]);
   for (int j= 0; j < deg; ++j) f[j + 1]= f_ee(f[j], f[j + 1]);
   for (int j= 0; j < deg; ++j) {
    const auto &e= t[v][j];
    if (int u= e.to;u != t.parent(v)) dp2[u]= f_ev(f_ee(f[j], b[j + 1]), v);
   }
   dp[v]= f_ev(f[deg], v);
  }
 return ReRootingData<T,C>(t, dp1, dp2, dp);
}
using namespace std;
namespace AOJGRL_5_A {
// https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n;
 cin >> n;
 Tree<int> tree(n);
 for (int i= 0; i < n - 1; ++i) {
  int s, t, w;
  cin >> s >> t >> w;
  tree.add_edge(s, t, w);
 }
 tree.build();
 auto f_ee= [&](int l, int r) { return max(l, r); };
 auto f_ve= [&](int d, int,const auto &e) { return d + e.cost; };
 auto f_ev= [&](int d, int) { return d; };
 auto dp = rerooting<int>(tree,f_ee,f_ve,f_ev,0);
 cout << *max_element(dp.begin(), dp.end()) << '\n';
 return 0;
}
}
namespace AOJ1595 {
// https://onlinejudge.u-aizu.ac.jp/challenges/sources/UOA/UAPC/1595
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int u, v;
  cin >> u >> v;
  tree.add_edge(--u,--v);
 }
 tree.build();
 auto f_ee= [&](int l, int r) { return max(l, r); };
 auto f_ve= [&](int d, int,auto) { return d + 1; };
 auto f_ev= [&](int d, int) { return d; };
 auto dp= rerooting<int>(tree,f_ee, f_ve, f_ev, 0);
 for (auto x: dp) cout << 2 * (N - 1) - x << '\n';
 return 0;
}
}

namespace yukicoder768 {
// https://yukicoder.me/problems/no/768
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int u, v;
  cin >> u >> v;
  tree.add_edge(--u,--v);
 }
 tree.build();
 auto f_ee= [&](bool l, bool r) { return l | r; };
 auto f_ve= [&](bool d, int,auto) { return d; };
 auto f_ev= [&](bool d, int) { return !d; };
 auto dp= rerooting<bool>(tree, f_ee, f_ve, f_ev, false);
 vector<int> ans;
 for (int i= 0; i < N; ++i)
  if (dp[i]) ans.push_back(i + 1);
 cout << ans.size() << '\n';
 for (int x: ans) cout << x << '\n';
 return 0;
}
}


namespace ABC222F {
// https://atcoder.jp/contests/abc222/tasks/abc222_f
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 Tree<long long> tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int A, B, C;
  cin >> A >> B >> C;
  tree.add_edge(--A,--B,C);
 }
 tree.build();
 vector<long long> D(N);
 for (int i= 0; i < N; ++i) cin >> D[i];
 auto f_ee= [&](long long l, long long r) { return max(l, r); };
 auto f_ve= [&](long long d, int, const auto& e) { return max(d, D[e.to]) + e.cost; };
 auto f_ev= [&](long long d, int) { return d; };
 auto dp= rerooting<long long>(tree, f_ee, f_ve, f_ev, 0ll);
 for (long long x: dp) cout << x << '\n';
 return 0;
}
}

namespace yukicoder1494 {
// https://yukicoder.me/problems/no/1494
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 string S;
 cin >> S;
 int n= S.length();
 Tree<char> tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int u, v;
  char c;
  cin >> u >> v >> c;
  tree.add_edge(--u,--v,c);
 }
 tree.build();
 using Data= vector<int>;
 auto f_ee= [&](const Data &l, const Data &r) {
  Data ret(n + 1);
  for (int i= 0; i <= n; ++i) ret[i]= max(l[i], r[i]);
  return ret;
 };
 auto f_ve= [&](Data d,int, const auto &e) {
  for (int i= n; i--;)
   if (S[i] == e.cost) d[i + 1]= max(d[i + 1], d[i] + 1);
  for (int i= 0; i < n; ++i) d[i + 1]= max(d[i + 1], d[i]);
  return d;
 };
 auto f_ev= [&](const Data &d, int) { return d; };
 auto dp= rerooting<Data>(tree, f_ee, f_ve, f_ev, Data(n + 1, 0));
 int ans= 0;
 for (const auto &v: dp) ans= max(ans, v[n]);
 cout << ans << '\n';
 return 0;
}
}

namespace yukicoder1418 {
// https://yukicoder.me/problems/no/1418
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int A, B;
  cin >> A >> B;
  tree.add_edge(--A,--B);
 }
 tree.build();
 using Data= array<int, 2>;
 auto f_ee= [&](const Data &l, const Data &r) { return Data{l[0] + r[0], l[1] + r[1]}; };
 auto f_ve= [&](const Data &d, int,auto) { return d; };
 auto f_ev= [&](Data d, int) {
  ++d[0], d[1]+= d[0];
  return d;
 };
 auto dp= rerooting<Data>(tree, f_ee, f_ve, f_ev, Data{0, 0});
 int ans= 0;
 for (const auto &x: dp) ans+= x[1];
 cout << ans << '\n';
 return 0;
}
}
namespace yukicoder922 {
// https://yukicoder.me/problems/no/922
// 森
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, Q;
 cin >> N >> M >> Q;
 Tree tree(N);
 for (int i= 0; i < M; ++i) {
  int u, v;
  cin >> u >> v;
  tree.add_edge(--u,--v);
 }
 tree.build();
 vector<int> cnt(N);
 int ans= 0;
 while (Q--) {
  int a, b;
  cin >> a >> b;
  --a, --b;
  if (tree.connected(a, b)) ans+= tree.dist(a, b);
  else ++cnt[a], ++cnt[b];
 }
 using Data= array<int, 2>;
 auto f_ee= [&](const Data &l, const Data &r) { return Data{l[0] + r[0], l[1] + r[1]}; };
 auto f_ve= [&](const Data &d, int, auto) { return Data{d[0], d[1] + d[0]}; };
 auto f_ev= [&](const Data &d, int v) { return Data{d[0] + cnt[v], d[1]}; };
 auto dp= rerooting<Data>(tree, f_ee, f_ve, f_ev, Data{0, 0});
 constexpr int INF= 1 << 30;
 vector<int> mi(N, INF);
 for (int i= 0; i < N; ++i) {
  int u= tree.root(i);
  mi[u]= min(mi[u], dp[i][1]);
 }
 for (int i= 0; i < N; ++i)
  if (mi[i] != INF) ans+= mi[i];
 cout << ans << '\n';
 return 0;
}
}

namespace yukicoder1075 {
// https://yukicoder.me/problems/no/1075
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<int(1e9 + 7)>;
 int N, K;
 cin >> N >> K;
 Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int a, b;
  cin >> a >> b;
  tree.add_edge(--a,--b);
 }
 tree.build();
 using Data= vector<Mint>;
 using DD= array<Data, 2>;
 auto f_ee= [&](const DD &l, const DD &r) {
  DD ret{Data(K), Data(K)};
  for (int i= 0; i < K; ++i) ret[0][i]= l[0][i] * r[0][i];
  for (int i= 0; i < K; ++i) ret[1][i]= l[1][i] * r[1][i];
  return ret;
 };
 auto f_ve= [&](DD d, int p, auto e) {
  if (p > e.to) {
   for (int i= K; --i;) d[1][i]= d[0][i - 1];
   d[1][0]= 0;
  }
  return d;
 };
 auto f_ev= [&](DD d, int) {
  for (int i= 1; i < K; ++i) d[0][i]+= d[0][i - 1];
  for (int i= 1; i < K; ++i) d[1][i]+= d[1][i - 1];
  return d;
 };
 auto dp= rerooting<DD>(tree, f_ee, f_ve, f_ev, DD{Data(K, 1), Data(K, 1)});
 Mint ans= 0;
 for (const auto &x: dp) ans+= x[1][K - 1];
 cout << ans << '\n';
 return 0;
}
}

namespace yukicoder1124 {
// https://yukicoder.me/problems/no/1124
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<int(1e9 + 7)>;
 int N;
 cin >> N;
 Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int A, B;
  cin >> A >> B;
  tree.add_edge(--A,--B);
 }
 tree.build();
 using Data= array<Mint, 2>;
 static constexpr Mint iv2= Mint(1) / 2;
 auto f_ee= [&](const Data &l, const Data &r) { return Data{l[0] + r[0], l[1] + l[0] * r[0] * 2 + r[1]}; };
 auto f_ve= [&](const Data &d, int, auto) { return Data{d[0] * iv2, d[1] * iv2}; };
 auto f_ev= [&](const Data &d, int) { return Data{d[0] + 1, d[1] + d[0] * 2 + 1}; };
 auto dp= rerooting<Data>(tree, f_ee, f_ve, f_ev, Data{0, 0});
 Mint ans= 0;
 for (const auto &x: dp) ans+= x[1];
 ans*= Mint(2).pow(N - 1);
 cout << ans << '\n';
 return 0;
}
}
namespace yukicoder1153 {
// https://yukicoder.me/problems/no/1153
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int A[M];
 for (int i= 0; i < M; ++i) cin >> A[i], --A[i];
Tree tree(N);
 for (int i= 0; i < N - 1; ++i) {
  int u, v;
  cin >> u >> v;
  tree.add_edge(--u,--v);
 }
 tree.build();
 auto mex= [](int v) -> int {
  for (int i= 0;; ++i)
   if (!((v>>i)&1)) return i;
 };
 auto f_ee= [&](int l, int r) { return l|r; };
 auto f_ve= [&](int g, int,auto) { return 1<<g; };
 auto f_ev= [&](int d, int) { return mex(d); };
 auto dp= rerooting<int>(tree, f_ee, f_ve, f_ev, 0);
 int sum= 0;
 for (int i= 0; i < M; ++i) sum^= dp[A[i]];
 if (sum) {
  for (int i= 0; i < M; ++i) {
   int v=A[i], g= dp[v], h=sum^g;
   if (h < g) 
    for(auto e:tree[v])if(int u=e.to;dp.get(v,u) == h){
     cout<<i+1<<" "<<u+1<<'\n';
     return 0;
    }
  }
 } else cout << -1 << " " << -1 << '\n';
 return 0;
}
}
namespace yukicoder1295{
//https://yukicoder.me/problems/no/1295
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;cin>>N;
 Tree tree(N);
 for(int i=0;i<N-1;++i){
  int a,b;cin>>a>>b;
  tree.add_edge(--a,--b);
 }
 tree.build();
 vector<int> ma(N),ma2(N),mi(N);
 for(int i=0;i<N;++i){
  vector<int> vs;
  for(auto e:tree[i])vs.push_back(e.to);
  sort(vs.begin(),vs.end());
  int n=vs.size();
  ma[i]=vs[n-1],mi[i]=vs[0];
  ma2[i]=n>1? vs[n-2]:-1;
 }
 auto f_ee=[&](int l,int r){return l+r;};
 auto f_ve=[&](int d,int p,auto e){
  if(d>=4||(d==3&&p!=ma[e.to]))return 4;
  if(d==0&&p==mi[e.to])return 0;
  if(e.to==ma[p]||e.to==mi[p])return 2;
  if(e.to==ma2[p])return 3;
  return 4;
 };
 auto f_ev=[&](int d,int){return d;};
 auto dp = rerooting<int>(tree,f_ee,f_ve,f_ev,0);
 for(auto x:dp){
  cout<<(x<=2? "Yes":"No")<<'\n';}
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // AOJGRL_5_A::main();
 // AOJ1595::main();
 // yukicoder768::main();
 // ABC222F::main();
 // yukicoder1494::main();
 // yukicoder1418::main();
 // yukicoder922::main();
 // yukicoder1075::main();
 // yukicoder1124::main();
 // yukicoder1153::main();
 yukicoder1295::main();
 return 0;
}
0