問題一覧 > 通常問題

No.1494 LCS on Tree

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : penguinman / テスター : kaage yuto1115
お気に入りにしたユーザー ProblemId : 6223 / 自分の提出
問題文最終更新日: 2021-04-28 07:54:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 293 (順位表) の他の問題:

Problem Statement

There is a tree with $N$ vertices, numbered from $1$ to $N$. The $i$-th edge bidirectionally connects vertex $u_i$ and vertex $v_i$, and has a lowercase English letter $c_i$ written on it.

For $x,\ y$ satisfying $1\leq x,\ y\leq N,\ x\neq y$, define $str(x,\ y)$ as follows.

  • The string obtained by concatenating the characters written on the edges passed through when moving from vertex $x$ to vertex $y$ along the shortest path, in the order they are passed

Since the given graph is a tree, $str(x,\ y)$ is uniquely determined.

Given a string $S$, choose $x,\ y$ appropriately to maximize the length of the longest common subsequence (LCS) of $S$ and $str(x,\ y)$.

Here, the longest common subsequence of strings $A,\ B$ is a longest string that is both a subsequence of $A$ and a subsequence of $B$, and a subsequence of a string $C$ is a string obtained by taking $0$ or more characters from $C$ and arranging them without changing their order.

Input

\(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$ is a lowercase English letter
  • $S$ consists only of lowercase English letters
  • The given graph is a tree
  • $N,\ u_i,\ v_i$ are integers

Output

Output the maximum length of the longest common subsequence of $S$ and $str(x,\ y)$.

Sample

Sample 1
Input
3
abc
1 2 a
2 3 b
Output
2

You can take $(x,\ y)=(1,\ 3)$.

Sample 2
Input
5
penguinman
2 3 n
1 4 a
2 4 a
2 5 n
Output
2
Sample 3
Input
7
tuspauih
1 3 a
2 4 c
4 5 n
4 6 i
1 7 h
2 3 i
Output
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。