No.1494 LCS on Tree
タグ : / 解いたユーザー数 42
作問者 :
penguinman
/ テスター :
kaage
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もしくは右上の雲マークをクリックしてアカウントを作成してください。