結果
問題 | 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 |
ソースコード
from collections import defaultdictfrom typing import List, Tuplefrom typing import Callable, Generic, List, TypeVarT = 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 = nself._decrement = decrementdef addEdge(self, u: int, v: int) -> None:u -= self._decrementv -= self._decrementself.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._decrementassert 0 <= root < self._nparents = [-1] * self._norder = [root]stack = [root]while stack:cur = stack.pop()for next in self.adjList[cur]:if next == parents[cur]:continueparents[next] = curorder.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:continuedp2[next] = resres = op(res, composition(dp1[next], cur, next, 0))res = e(cur)for next in self.adjList[cur][::-1]:if parents[cur] == next:continuedp2[next] = op(res, dp2[next])res = op(res, composition(dp1[next], cur, next, 0))dp1[cur] = resfor 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 dp1def 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 resdef 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 resR = Rerooting[List[int]](n)weights = [defaultdict(str) for _ in range(n)]for u, v, c in edges:R.addEdge(u, v)weights[u][v] = cweights[v][u] = cdp = 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))