소프티어

처음에 각 리프노드까지의 경로에 대해서 행복값 찾는 코드로는 타임아웃나는 테스트 케이스가 하나 있어서 여기저기 참고해서 코드를 고쳐봤는데요. 각 단계에서 dp 를 계산하고 다음으로 넘기는 방식을 고안해 봤는데 기본으로 주어지는 테스트케이스는 성공하는데 나머지는 다 실패하는거 같아요. 제가 이런 저런 테스트 케이스 만들어봐도 제가 만든 건 다 예상값이 나오는데. 혹시 어디서 잘못되었는지 도와주시면 감사하겠습니다ㅠㅜ

import sys
sys.setrecursionlimit(1000000000)

input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
S = input().rstrip()

T = {i+1: set() for i in range(n)}

for _ in range(n-1):
    u, v, c = list(input().rstrip().split())
    u, v = int(u), int(v)

    T[u].add((v, c))
    T[v].add((u, c))
    

res = 0

def dfs(node, parent, prevDP):
    global res

    newDP = [0]*(m+1)

    for i in range(1, 1+m):
        if parent == None: break
            
        if parent[1] == S[i-1]: newDP[i] = prevDP[i-1]+1
        else: newDP[i] = max(prevDP[i], newDP[i-1])
            

    for neighbor in T[node]:
        if parent==None or neighbor[1] != parent[1]:
            dfs(neighbor[0], (node, neighbor[1]), newDP)
            
    if node != 1 and len(T[node])==1: 

        res = max(res, newDP[-1])
        return


dfs(1, None, [0]*(m+1))
print(res)