結果
問題 | No.900 aδδitivee |
ユーザー | toyuzuko |
提出日時 | 2020-05-15 20:57:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 985 ms / 2,000 ms |
コード長 | 4,986 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 126,660 KB |
最終ジャッジ日時 | 2023-10-19 11:37:28 |
合計ジャッジ時間 | 21,877 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
52,888 KB |
testcase_01 | AC | 40 ms
52,912 KB |
testcase_02 | AC | 45 ms
59,484 KB |
testcase_03 | AC | 47 ms
59,744 KB |
testcase_04 | AC | 46 ms
59,492 KB |
testcase_05 | AC | 48 ms
59,500 KB |
testcase_06 | AC | 47 ms
59,488 KB |
testcase_07 | AC | 938 ms
124,288 KB |
testcase_08 | AC | 985 ms
124,532 KB |
testcase_09 | AC | 908 ms
124,512 KB |
testcase_10 | AC | 913 ms
124,732 KB |
testcase_11 | AC | 967 ms
125,460 KB |
testcase_12 | AC | 933 ms
124,904 KB |
testcase_13 | AC | 867 ms
124,744 KB |
testcase_14 | AC | 914 ms
125,444 KB |
testcase_15 | AC | 918 ms
125,956 KB |
testcase_16 | AC | 891 ms
124,552 KB |
testcase_17 | AC | 922 ms
124,540 KB |
testcase_18 | AC | 938 ms
124,416 KB |
testcase_19 | AC | 882 ms
124,580 KB |
testcase_20 | AC | 921 ms
126,064 KB |
testcase_21 | AC | 942 ms
126,552 KB |
testcase_22 | AC | 551 ms
126,188 KB |
testcase_23 | AC | 532 ms
126,496 KB |
testcase_24 | AC | 523 ms
126,248 KB |
testcase_25 | AC | 568 ms
126,568 KB |
testcase_26 | AC | 523 ms
126,108 KB |
testcase_27 | AC | 535 ms
126,660 KB |
testcase_28 | AC | 523 ms
126,052 KB |
ソースコード
class Tree(): #weighted def __init__(self, n, edge): self.n = n self.tree = [[] for _ in range(n)] for e in edge: self.tree[e[0]].append((e[1], e[2])) self.tree[e[1]].append((e[0], e[2])) def setroot(self, root): self.root = root self.parent = [None for _ in range(self.n)] self.parent[root] = -1 self.depth = [None for _ in range(self.n)] self.depth[root] = 0 self.distance = [None for _ in range(self.n)] self.distance[root] = 0 self.order = [] self.order.append(root) self.cost = [0 for _ in range(self.n)] self.size = [1 for _ in range(self.n)] stack = [root] while stack: node = stack.pop() for adj, cost in self.tree[node]: if self.parent[adj] is None: self.parent[adj] = node self.depth[adj] = self.depth[node] + 1 self.distance[adj] = self.distance[node] + cost self.cost[adj] = cost self.order.append(adj) stack.append(adj) for node in self.order[::-1]: for adj, cost in self.tree[node]: if self.parent[node] == adj: continue self.size[node] += self.size[adj] def heavylight_decomposition(self): self.order = [None for _ in range(self.n)] self.head = [None for _ in range(self.n)] self.head[self.root] = self.root self.next = [None for _ in range(self.n)] stack = [self.root] order = 0 while stack: node = stack.pop() self.order[node] = order order += 1 maxsize = 0 for adj, cost in self.tree[node]: if self.parent[node] == adj: continue if maxsize < self.size[adj]: maxsize = self.size[adj] self.next[node] = adj for adj, cost in self.tree[node]: if self.parent[node] == adj or self.next[node] == adj: continue self.head[adj] = adj stack.append(adj) if self.next[node] is not None: self.head[self.next[node]] = self.head[node] stack.append(self.next[node]) def range_hld(self, u, v, edge=False): res = [] while True: if self.order[u] > self.order[v]: u, v = v, u if self.head[u] != self.head[v]: res.append((self.order[self.head[v]], self.order[v] + 1)) v = self.parent[self.head[v]] else: res.append((self.order[u] + edge, self.order[v] + 1)) return res def subtree_hld(self, u, edge=False): return self.order[u] + edge, self.order[u] + self.size[u] def lca_hld(self, u, v): while True: if self.order[u] > self.order[v]: u, v = v, u if self.head[u] != self.head[v]: v = self.parent[self.head[v]] else: return u class BinaryIndexedTree(): #1-indexed def __init__(self, n): self.n = n self.tree = [0 for _ in range(n + 1)] def sum(self, idx): res = 0 while idx: res += self.tree[idx] idx -= idx & -idx return res def add(self, idx, x): while idx <= self.n: self.tree[idx] += x idx += idx & -idx def bisect_left(self, x): if x <= 0: return 0 res, tmp = 0, 2**((self.n).bit_length() - 1) while tmp: if res + tmp <= self.n and self.tree[res + tmp] < x: x -= self.tree[res + tmp] res += tmp tmp >>= 1 return res + 1 class RAQandRSQ(): def __init__(self, n): self.bit1 = BinaryIndexedTree(n) self.bit2 = BinaryIndexedTree(n) def add(self, lt, rt, x): self.bit1.add(lt + 1, -x * (lt)) self.bit1.add(rt + 1, x * (rt)) self.bit2.add(lt + 1, x) self.bit2.add(rt + 1, -x) def sum(self, lt, rt): rsum = self.bit2.sum(rt) * (rt) + self.bit1.sum(rt) lsum = self.bit2.sum(lt) * (lt) + self.bit1.sum(lt) return rsum - lsum import sys input = sys.stdin.readline N = int(input()) E = [tuple(map(int, input().split())) for _ in range(N - 1)] T = Tree(N, E) T.setroot(0) T.heavylight_decomposition() R = RAQandRSQ(N) for i in range(N): R.add(T.order[i], T.order[i] + 1, T.cost[i]) Q = int(input()) res = list() for _ in range(Q): q = tuple(map(int, input().split())) if q[0] == 1: a, x = q[1:] lt, rt = T.subtree_hld(a, True) R.add(lt, rt, x) else: b = q[1] s = 0 for lt, rt in T.range_hld(0, b, True): s += R.sum(lt, rt) res.append(s) print('\n'.join(map(str, res)))