結果

問題 No.1494 LCS on Tree
ユーザー penguinman
提出日時 2021-04-25 03:23:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,301 bytes
コンパイル時間 120 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 80,384 KB
最終ジャッジ日時 2024-07-04 09:24:56
合計ジャッジ時間 3,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import resource
sys.setrecursionlimit(3000)
N = int(input())
S = input()
flag = [False]*N
edge = [[]for i in range(N)]
char = [[]for i in range(N)]
for i in range(N-1):
    x, y, z = input().split()
    x = int(x)-1
    y = int(y)-1
    edge[x].append(y)
    edge[y].append(x)
    char[x].append(z)
    char[y].append(z)
M = len(S)
dp = [[0]*(M+1) for i in range(N)]
rev = [[0]*(M+1) for i in range(N)]
ans = 0

def dfs(now):
    global dp
    global rev
    global ans
    flag[now] = True
    for k in range(len(edge[now])):
        nex = edge[now][k]
        if flag[nex]:
            continue
        dfs(nex)
        for i in reversed(range(M)):
            if S[i] == char[now][k]:
                dp[nex][i+1] = max(dp[nex][i+1], dp[nex][i]+1)
        for i in range(M):
            dp[nex][i+1] = max(dp[nex][i+1], dp[nex][i])
        for i in range(M):
            if S[i] == char[now][k]:
                rev[nex][i] = max(rev[nex][i], rev[nex][i+1]+1)
        for i in reversed(range(M)):
            rev[nex][i] = max(rev[nex][i], rev[nex][i+1])
        for i in range(M+1):
            ans = max(ans, dp[now][i]+rev[nex][i], rev[now][i]+dp[nex][i])
            dp[now][i] = max(dp[now][i], dp[nex][i])
            rev[now][i] = max(rev[now][i], rev[nex][i])

dfs(0)
print(ans)
0