No.1494 LCS on Tree
タグ : / 解いたユーザー数 38
作問者 :
penguinman
/ テスター :
kaage
yuto1115
問題文
$N$ 頂点の木があり、各頂点には $1$ から $N$ までの数字が割り振られています。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでおり、また英小文字 $c_i$ が書かれています。
$1\leq x,\ y\leq N,\ x\neq y$ を満たす $x,\ y$ に対して、$str(x,\ y)$ を以下のように定めます。
- 頂点 $x$ から頂点 $y$ まで最短距離で移動する際に通る辺に書かれた文字を、通る順に並べて連結した文字列
与えられるグラフが木であることから、$str(x,\ y)$ は一意に定まります。
文字列 $S$ が与えられるので、適切に $x,\ y$ を選ぶことで $S$ と $str(x,\ y)$ の最長共通部分列 (LCS) の長さを最大化してください。
ここで、ある文字列 $A,\ B$ の最長共通部分列とは $A$ の部分列かつ $B$ の部分列である最長の文字列のことを指し、また、文字列 $C$ の部分列とは $C$ から $0$ 文字以上を取り出して順序を変えずに並べたもののことを指します。
入力
\(N\)
\(S\)
\(u_1\) \(v_1\) \(c_1\)
\(u_2\) \(v_2\) \(c_2\)
\(\vdots\)
\(u_{N-1}\) \(v_{N-1}\) \(c_{N-1}\)
- $2\leq N\leq 2000$
- $1\leq |S|\leq 2000$
- $1\leq u_i\lt v_i\leq N$
- $c_i$ は英小文字
- $S$ は英小文字のみからなる
- 与えられるグラフは木
- $N,\ u_i,\ v_i$ は整数
出力
$S$ と $str(x,\ y)$ の最長共通部分列の長さの最大値を出力してください。
サンプル
サンプル1
入力
3 abc 1 2 a 2 3 b
出力
2
$(x,\ y)=(1,\ 3)$ とすれば良いです。
サンプル2
入力
5 penguinman 2 3 n 1 4 a 2 4 a 2 5 n
出力
2
サンプル3
入力
7 tuspauih 1 3 a 2 4 c 4 5 n 4 6 i 1 7 h 2 3 i
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。