結果
問題 | No.1718 Random Squirrel |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-26 20:47:11 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,579 ms / 2,000 ms |
コード長 | 3,583 bytes |
コンパイル時間 | 82 ms |
コンパイル使用メモリ | 12,356 KB |
実行使用メモリ | 93,844 KB |
最終ジャッジ日時 | 2023-10-19 13:52:18 |
合計ジャッジ時間 | 23,335 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
11,140 KB |
testcase_01 | AC | 39 ms
11,140 KB |
testcase_02 | AC | 42 ms
11,140 KB |
testcase_03 | AC | 39 ms
11,140 KB |
testcase_04 | AC | 38 ms
11,140 KB |
testcase_05 | AC | 38 ms
11,140 KB |
testcase_06 | AC | 39 ms
11,140 KB |
testcase_07 | AC | 40 ms
11,144 KB |
testcase_08 | AC | 39 ms
11,140 KB |
testcase_09 | AC | 39 ms
11,144 KB |
testcase_10 | AC | 38 ms
11,140 KB |
testcase_11 | AC | 999 ms
65,820 KB |
testcase_12 | AC | 173 ms
21,524 KB |
testcase_13 | AC | 615 ms
44,668 KB |
testcase_14 | AC | 1,112 ms
68,164 KB |
testcase_15 | AC | 813 ms
60,992 KB |
testcase_16 | AC | 381 ms
34,756 KB |
testcase_17 | AC | 904 ms
63,284 KB |
testcase_18 | AC | 1,185 ms
78,840 KB |
testcase_19 | AC | 819 ms
58,348 KB |
testcase_20 | AC | 368 ms
31,348 KB |
testcase_21 | AC | 1,431 ms
89,556 KB |
testcase_22 | AC | 1,391 ms
93,052 KB |
testcase_23 | AC | 1,579 ms
89,508 KB |
testcase_24 | AC | 1,433 ms
89,512 KB |
testcase_25 | AC | 1,420 ms
93,844 KB |
testcase_26 | AC | 904 ms
89,660 KB |
testcase_27 | AC | 941 ms
88,976 KB |
testcase_28 | AC | 905 ms
89,660 KB |
testcase_29 | AC | 941 ms
91,812 KB |
testcase_30 | AC | 957 ms
93,340 KB |
testcase_31 | AC | 945 ms
91,800 KB |
testcase_32 | AC | 946 ms
91,812 KB |
ソースコード
from collections import defaultdict from typing import List, Tuple INF = int(1e18) def randomSquirrel(n: int, edges: List[Tuple[int, int]], sweets: List[int]) -> List[int]: E = Tuple[int, int] # (maxDist, mustVisitCount) def e(root: int) -> E: return (0, 0) if isSpecial[root] else (-INF, 0) def op(childRes1: E, childRes2: E) -> E: dist1, must1 = childRes1 dist2, must2 = childRes2 return (max(dist1, dist2), must1 + must2) def composition(fromRes: E, parent: int, cur: int, direction: int) -> E: """direction: 0: cur -> parent, 1: parent -> cur""" dist, must = fromRes w = weights[cur][parent] if direction == 0 else weights[parent][cur] # dist>=0 才开始算入必须经过的路径 return (dist + w, must + 1) if dist >= 0 else (dist, must) isSpecial = [False] * n for v in sweets: isSpecial[v] = True R = Rerooting(n) weights = [defaultdict(int) for _ in range(n)] for u, v in edges: R.addEdge(u, v) weights[u][v] = 1 weights[v][u] = 1 dp = R.rerooting(e=e, op=op, composition=composition, root=0) res = [mustVisit * 2 - maxDist for maxDist, mustVisit in dp] # 可以不回到出发点,2*点数-最大距离 return res 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 if __name__ == "__main__": n, k = map(int, input().split()) edges = [] for _ in range(n - 1): u, v = map(int, input().split()) u, v = u - 1, v - 1 edges.append((u, v)) sweets = [int(x) - 1 for x in input().split()] print(*randomSquirrel(n, edges, sweets), sep="\n")