[solution] Ghoul-icious Goodies solution codechef

Problem solution codechef

Despite my ghoulish reputation, I really have the heart of a small boy. I keep it in a jar on my desk.

Alice wants to give Bob some goodies, but she’s uncertain about how many to give.
To help determine the quantity, she presented Bob with the following challenge:

Alice has a tree, i.e, a simple connected undirected graph with  vertices and �−1 edges.
Each edge has a lowercase character written on it.
Alice also has a string  of length , consisting of lowercase characters.

Define str(�,�) to be the string formed by the characters seen while traversing the edges on the unique path from  to  in the tree.

Alice asks Bob to choose two vertices  and , and will give him LCS(str(�,�),�) goodies.

Here, LCS(�,�) denotes the length of the longest common subsequence of strings  and .
For example, LCS(“aba”, “cd”)=0,LCS(“aba”, “aa”)=2, and LCS(“abc”, “cba”)=1.

If Bob chooses  and  optimally, what’s the maximum number of goodies he can receive?

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer  — the number of vertices.
    • The next �−1 lines describe the edges. The -th of these �−1 lines contains two space-separated integers �� and ��, denoting an edge between �� and �� and a character �� written on the edge.
    • The final line contains Alice’s string , consisting of lowercase letters.

Output Format

For each test case, output on a new line the maximum number of goodies Bob can get.

Constraints

  • 1≤�≤500
  • 2≤�≤104
  • 1≤��,��≤�
  • The input graph is a tree on  vertices.
  • �� is a lowercase Latin letter, i.e, between 'a' and 'z‘.
  • 1≤∣�∣≤103
  • The sum of  across all test cases won’t exceed 104.
  • The sum of ∣�∣ across all test cases won’t exceed 103.

Sample 1:

Input

Output

3
6
1 2 a
2 3 c
2 4 d
1 5 b
3 6 d
abcd
5
1 2 a
2 3 c
2 4 d
1 5 b
cfgd
3
1 3 a
2 3 a
b
3
2
0

Explanation:

Test case 1: The tree looks like this:

Bob can select �=1 and �=6.
The �→� path is 1→2→3→6, which results in the string “acd”.
LCS(“acd”, “abcd”)=3, which is the best Bob can do.

Test case 2: The tree looks like this:

Bob can choose �=3 and �=4 to obtain the string “cd”, whose LCS with �=”cfgd” is 2.

Leave a Comment