結果

問題 No.1494 LCS on Tree
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-14 10:10:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 697 ms / 2,000 ms
コード長 3,411 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 296,116 KB
最終ジャッジ日時 2024-11-20 15:10:36
合計ジャッジ時間 21,049 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import defaultdict
from typing import List, Tuple
from typing import Callable, Generic, List, TypeVar
T = TypeVar("T")
class Rerooting(Generic[T]):
__slots__ = ("adjList", "_n", "_decrement")
def __init__(self, n: int, decrement: int = 0):
self.adjList = [[] for _ in range(n)]
self._n = n
self._decrement = decrement
def addEdge(self, u: int, v: int) -> None:
u -= self._decrement
v -= self._decrement
self.adjList[u].append(v)
self.adjList[v].append(u)
def rerooting(
self,
e: Callable[[int], T],
op: Callable[[T, T], T],
composition: Callable[[T, int, int, int], T],
root=0,
) -> List["T"]:
root -= self._decrement
assert 0 <= root < self._n
parents = [-1] * self._n
order = [root]
stack = [root]
while stack:
cur = stack.pop()
for next in self.adjList[cur]:
if next == parents[cur]:
continue
parents[next] = cur
order.append(next)
stack.append(next)
dp1 = [e(i) for i in range(self._n)]
dp2 = [e(i) for i in range(self._n)]
for cur in order[::-1]:
res = e(cur)
for next in self.adjList[cur]:
if parents[cur] == next:
continue
dp2[next] = res
res = op(res, composition(dp1[next], cur, next, 0))
res = e(cur)
for next in self.adjList[cur][::-1]:
if parents[cur] == next:
continue
dp2[next] = op(res, dp2[next])
res = op(res, composition(dp1[next], cur, next, 0))
dp1[cur] = res
for newRoot in order[1:]:
parent = parents[newRoot]
dp2[newRoot] = composition(op(dp2[newRoot], dp2[parent]), parent, newRoot, 1)
dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])
return dp1
def lcsOnTree(n: int, edges: List[Tuple[int, int, str]], target: str) -> int:
def e(root: int) -> List[int]:
return [0] * (len(target) + 1)
def op(childRes1: List[int], childRes2: List[int]) -> List[int]:
res = childRes1[:]
for i in range(len(res)):
res[i] = max(res[i], childRes2[i])
return res
def composition(fromRes: List[int], parent: int, cur: int, direction: int) -> List[int]:
"""direction: 0: cur -> parent, 1: parent -> cur"""
from_, to = (cur, parent) if direction == 0 else (parent, cur)
c = weights[from_][to]
res = fromRes[:]
for i in range(len(s) - 1, -1, -1):
if s[i] == c:
res[i + 1] = max(res[i + 1], res[i] + 1)
for i in range(len(s)):
res[i + 1] = max(res[i + 1], res[i])
return res
R = Rerooting[List[int]](n)
weights = [defaultdict(str) for _ in range(n)]
for u, v, c in edges:
R.addEdge(u, v)
weights[u][v] = c
weights[v][u] = c
dp = R.rerooting(e=e, op=op, composition=composition, root=0)
return max(v[-1] for v in dp)
if __name__ == "__main__":
n = int(input())
s = input()
edges = []
for _ in range(n - 1):
u, v, c = input().split()
edges.append((int(u) - 1, int(v) - 1, c))
print(lcsOnTree(n, edges, s))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0