소프티어

#include<iostream>
#include<vector>
#include<string>


using namespace std;


int N, M;
string S;
bool *visited;
vector<pair<int, char>> *tree;
int dp[5005][5005] = {0,};
int lcs = 0;


void dfs(int num, int depth){
    bool is_leaf = true;
    visited[num] = true;
    for(pair<int, char> p : tree[num]){
        if(!visited[p.first]){
            visited[p.first] = true;
            is_leaf = false;
            for(int i = 1; i <= S.length(); i++){
                if(S[i - 1] == p.second){
                    dp[depth][i] = dp[depth - 1][i - 1] + 1;
                }else{
                    dp[depth][i] = dp[depth - 1][i] > dp[depth][i - 1] ? dp[depth - 1][i] : dp[depth][i - 1]; 
                }
            }
            dfs(p.first, depth + 1);
            for(int i = 1; i <= S.length(); i++){
                dp[depth][i] = 0;
            }
        }
    }
    if(is_leaf){
        if(dp[depth - 1][S.length()] > lcs) lcs = dp[depth - 1][S.length()];
    }
}


int main(int argc, char** argv)
{
    cin >> N >> M;


    cin >> S;


    tree = new vector<pair<int, char>>[N + 1];
    visited = new bool[N + 1];
    for(int i = 0; i < N; i++){
        visited[i] = false;
    }


    for(int i = 0; i < N - 1; i++){
        int u, v;
        char c;
        cin >> u >> v >> c;
        tree[u].push_back({v, c});
        tree[v].push_back({u, c});
    }


    dfs(1, 1);


    cout << lcs;
    
   return 0;
}

시간 초과는 뜨지 않고 테스트케이스 6, 12, 18, 20 번만 오답 뜨는데 이유를 모르겠네요ㅜ 도와주실 분 계신가요ㅠㅠ