結果
問題 | No.1637 Easy Tree Query |
ユーザー | titan23 |
提出日時 | 2022-06-28 12:21:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 275 ms / 2,000 ms |
コード長 | 4,532 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 101,620 KB |
最終ジャッジ日時 | 2024-05-01 03:23:34 |
合計ジャッジ時間 | 9,520 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
53,120 KB |
testcase_01 | AC | 36 ms
53,120 KB |
testcase_02 | AC | 184 ms
100,896 KB |
testcase_03 | AC | 36 ms
53,640 KB |
testcase_04 | AC | 142 ms
89,052 KB |
testcase_05 | AC | 152 ms
85,632 KB |
testcase_06 | AC | 131 ms
82,676 KB |
testcase_07 | AC | 88 ms
77,708 KB |
testcase_08 | AC | 128 ms
86,272 KB |
testcase_09 | AC | 196 ms
95,012 KB |
testcase_10 | AC | 111 ms
81,240 KB |
testcase_11 | AC | 269 ms
97,612 KB |
testcase_12 | AC | 198 ms
91,784 KB |
testcase_13 | AC | 103 ms
81,528 KB |
testcase_14 | AC | 194 ms
92,888 KB |
testcase_15 | AC | 228 ms
98,212 KB |
testcase_16 | AC | 242 ms
100,792 KB |
testcase_17 | AC | 110 ms
81,620 KB |
testcase_18 | AC | 154 ms
85,384 KB |
testcase_19 | AC | 159 ms
86,400 KB |
testcase_20 | AC | 198 ms
91,332 KB |
testcase_21 | AC | 165 ms
89,212 KB |
testcase_22 | AC | 249 ms
101,620 KB |
testcase_23 | AC | 114 ms
82,932 KB |
testcase_24 | AC | 158 ms
89,344 KB |
testcase_25 | AC | 153 ms
84,300 KB |
testcase_26 | AC | 190 ms
93,068 KB |
testcase_27 | AC | 275 ms
99,968 KB |
testcase_28 | AC | 134 ms
83,712 KB |
testcase_29 | AC | 169 ms
90,992 KB |
testcase_30 | AC | 160 ms
91,136 KB |
testcase_31 | AC | 88 ms
76,544 KB |
testcase_32 | AC | 131 ms
84,864 KB |
testcase_33 | AC | 129 ms
81,280 KB |
testcase_34 | AC | 119 ms
100,700 KB |
ソースコード
import sys input = lambda: sys.stdin.readline().rstrip() class RootedTree: def __init__(self, G: list, root: int): self._n = len(G) self._G = G self._root = root self._height = -1 self._toposo = [] self._dist = [] self._descendant_num = [] self._child = [] self._child_num = [] self._parents = [] self._diameter = -1 self._bipartite_graph = [] self._calc_dist_toposo() # self._calc_child_parents() def __len__(self) -> int: "Return the number of vertex of self. / O(1)" return self._n def __str__(self) -> str: "Print Rooted Tree. / O(N) or O(1)" self._calc_child_parents() ret = ["<RootedTree> ["] ret.extend( [f' dist:{d} - v:{str(i).zfill(2)} - p:{str(self._parents[i]).zfill(2)} - child:{self._child[i]}' for i,d in sorted(enumerate(self._dist), key=lambda x: x[1])] ) ret.append(']') return '\n'.join(ret) def _calc_dist_toposo(self) -> None: "Calc dist and toposo. / O(N)" todo = [self._root] self._dist = [-1] * self._n self._dist[self._root] = 0 self._toposo = [self._root] while todo: v = todo.pop() d = self._dist[v] for x,c in self._G[v]: if self._dist[x] != -1: continue self._dist[x] = d + c todo.append(x) self._toposo.append(x) return def _calc_child_parents(self) -> None: "Calc child and parents. / O(N)" if self._child and self._child_num and self._parents: return self._child_num = [0] * self._n self._child = [[] for _ in range(self._n)] self._parents = [-1] * self._n for v in self._toposo[::-1]: for x,c in self._G[v]: if self._dist[x] < self._dist[v]: self._parents[v] = x continue self._child[v].append(x) self._child_num[v] += 1 return def get_dist(self) -> list: "Return dist. / O(N)" return self._dist def get_toposo(self) -> list: "Return toposo. / O(N)" return self._toposo def get_height(self) -> int: "Return height. / O(N)" if self._height > -1: return self._height self._height = max(self._dist) return self._height def get_descendant_num(self) -> list: "Return descendant_num. / O(N)" if self._descendant_num: return self._descendant_num self._descendant_num = [1] * self._n for v in self._toposo[::-1]: for x,c in self._G[v]: if self._dist[x] < self._dist[v]: continue self._descendant_num[v] += self._descendant_num[x] for i in range(self._n): self._descendant_num[i] -= 1 return self._descendant_num def get_child(self) -> list: "Return child / O(N)" if self._child: return self._child self._calc_child_parents() return self._child def get_child_num(self) -> list: "Return child_num. / O(N)" if self._child_num: return self._child_num self._calc_child_parents() return self._child_num def get_parents(self) -> list: "Return parents. / O(N)" if self._parents: return self._parents self._calc_child_parents() return self._parents def get_diameter(self) -> int: "Return diameter of tree. / O(N)" if self._diameter > -1: return self._diameter s = self._dist.index(self.get_height()) todo = [s] ndist = [-1] * self._n ndist[s] = 0 while todo: v = todo.pop() d = ndist[v] for x, c in self._G[v]: if ndist[x] != -1: continue ndist[x] = d + c todo.append(x) self._diameter = max(ndist) return self._diameter def get_bipartite_graph(self) -> list: "Return [1 if root else 0]. / O(N)" if self._bipartite_graph: return self._bipartite_graph self._bipartite_graph = [-1] * self._n self._bipartite_graph[self._root] = 1 todo = [self._root] while todo: v = todo.pop() nc = 0 if self._bipartite_graph[v] else 1 for x,_ in self._G[v]: if self._bipartite_graph[x] != -1: continue self._bipartite_graph[x] = nc todo.append(x) return self._bipartite_graph # ----------------------- # n, q = map(int, input().split()) G = [[] for _ in range(n)] for _ in range(n-1): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append((b, 1)) G[b].append((a, 1)) tree = RootedTree(G, 0) dnum = tree.get_descendant_num() now = 0 for _ in range(q): p, x = map(int, input().split()) p -= 1 now += (dnum[p]+1) * x print(now)