소프티어

import sys
sys.setrecursionlimit(10000)
n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
h = [[""]*(n+1) for _ in range(n+1)]

graph = [ [] for _ in range(n+1)]

for i in range(n-1) :
    u, v, c = map(str, sys.stdin.readline().split())
    u, v = int(u), int(v)
    h[u][v] = str(c)
    h[v][u] = str(c)
    graph[u].append(v)
    graph[v].append(u)

#print(graph)
visited = [0] * (n+1)
visited[1] = 1
ans = -1
def LCS(b) :
    global ans
    a_len = len(s)
    b_len = len(b)
    d = [[0]*(b_len+1) for _ in range(a_len+1)]
    for i in range(1, a_len+1) :
        for j in range(1, b_len+1) :
            if s[i-1] == b[j-1] :
                d[i][j] = d[i-1][j-1] + 1
            else :
                d[i][j] = max(d[i-1][j], d[i][j-1])            
    if ans < d[a_len][b_len] :
        ans = d[a_len][b_len]
    
def dfs(u, road) :
    global visited
    #print(u, end= " ")
    #print(road)
    flag = 0
    for v in graph[u] :
        if visited[v] == 0 :
            flag = 1
            visited[v] = 1
            dfs(v, road+h[u][v])
            visited[v] = 0
    if flag == 0 :
        #print(road)
        LCS(road)
        return
        
dfs(1,"")

print(ans)

20개 중 5개 케이스에 대해서 시간초과가 나는데 어떤 방법으로 해결하면 좋을지 의견을 구합니다.