結果
問題 | No.1038 TreeAddQuery |
ユーザー |
👑 |
提出日時 | 2023-07-08 14:53:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,310 ms / 4,000 ms |
コード長 | 6,044 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,492 KB |
実行使用メモリ | 250,268 KB |
最終ジャッジ日時 | 2024-07-22 10:18:55 |
合計ジャッジ時間 | 27,977 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
class CentroidDecomposition:def __init__(self, n, edges=None):self.n = nself.par = [-1] * n # 重心分解木の親self.depth = [-1] * n # 重心分解木の深さself.size = [-1] * n # 重心分解木の部分木のサイズself.childcnt = [0] * n # 重心分解木の子の数if edges is None:self.edges = [[] for _ in range(n)]else:self.edges = edges# コピーしてないので注意self.centroids = [] # centroids[i] := 深さが i の重心のリストself.treeind = [] # treeind[j * logn + i] := 頂点 j が深さ i の重心の何番目の部分木かself.cent_dist = [] # cent_dist[j * logn + i] := 頂点 j が深さ i の重心からの距離def add_edge(self, u, v):self.edges[u].append(v)self.edges[v].append(u)def read_edges(self, indexed=1):for _ in range(self.n - 1):u, v = map(int, input().split())u -= indexedv -= indexedself.add_edge(u, v)def build(self):stack = [(0, -1, 0, -1)]while stack:pos, bpos, d, c = stack.pop()st = [pos]route = []sz = 0if len(self.treeind) == d * self.n:self.treeind += [-1] * self.nself.cent_dist += [-1] * self.nself.centroids.append([])if d >= 1:self.cent_dist[(d - 1) * self.n + pos] = 1while st:pos = st.pop()self.depth[pos] = -2route.append(pos)sz += 1if d >= 1:self.treeind[(d - 1) * self.n + pos] = cfor npos in self.edges[pos]:if self.depth[npos] == -1:st.append(npos)if d >= 1:self.cent_dist[(d - 1) * self.n + npos] = (self.cent_dist[(d - 1) * self.n + pos] + 1)g = -1for pos in route[::-1]:self.size[pos] = 1self.depth[pos] = -1if g != -1:continueisg = Truefor npos in self.edges[pos]:if self.depth[npos] == -1:self.size[pos] += self.size[npos]if self.size[npos] * 2 > sz:isg = Falsebreakif isg and 2 * self.size[pos] >= sz:g = posself.centroids[d].append(g)self.size[g] = szself.par[g] = bposself.depth[g] = dself.cent_dist[d * self.n + g] = 0if sz != 1:c = 0for npos in self.edges[g]:if self.depth[npos] == -1:stack.append((npos, g, d + 1, c))c += 1self.childcnt[g] = cself.logn = len(self.centroids)nex = [0] * (self.n * self.logn)for i in range(self.n):for j in range(self.logn):nex[i * self.logn + j] = self.cent_dist[j * self.n + i]self.cent_dist = nex[:]for i in range(self.n):for j in range(self.logn):nex[i * self.logn + j] = self.treeind[j * self.n + i]self.treeind = nex[:]def cent_ind_dist(self, u):"""u + u の各先祖の {頂点番号, 距離} を返す"""ret = [(u, 0)]v = ufor d in range(self.depth[u] - 1, -1, -1):v = self.par[v]ret.append((v, self.cent_dist[u * self.logn + d]))return retclass BIT:def __init__(self, n):self.n = nself.data = [0] * (n + 1)if n == 0:self.n0 = 0else:self.n0 = 1 << (n.bit_length() - 1)def sum_(self, i):s = 0while i > 0:s += self.data[i]i -= i & -ireturn sdef sum(self, l, r=-1):if r == -1:return self.sum_(l)else:return self.sum_(r) - self.sum_(l)def get(self, i):return self.sum(i, i + 1)def add(self, i, x):i += 1while i <= self.n:self.data[i] += xi += i & -idef lower_bound(self, x):if x <= 0:return 0i = 0k = self.n0while k > 0:if i + k <= self.n and self.data[i + k] < x:x -= self.data[i + k]i += kk //= 2return i + 1import sysinput = sys.stdin.readlinen, Q = map(int, input().split())G = CentroidDecomposition(n)G.read_edges()G.build()logn = len(G.centroids)bit = [BIT(n) for _ in range(logn)]subbit = [BIT(2 * n) for _ in range(logn)]L = [0] * nsubL = [0] * nfor d in range(logn):c = 0c2 = 0for g in G.centroids[d]:L[g] = cif d != 0:subL[g] = c2c += G.size[g]c2 += G.size[g] + 1def add(x, y, z):bg = -1for g, d in G.cent_ind_dist(x):dd = y - dif dd >= 0:bit[G.depth[g]].add(L[g], z)bit[G.depth[g]].add(L[g] + min(dd + 1, G.size[g]), -z)if bg != -1:subbit[G.depth[g]].add(subL[bg] + 1, z)subbit[G.depth[g]].add(subL[bg] + min(dd + 1, G.size[bg] + 1), -z)bg = gdef get(x):bg = -1ret = 0for g, d in G.cent_ind_dist(x):ret += bit[G.depth[g]].sum(L[g] + d + 1)if bg != -1:ret -= subbit[G.depth[g]].sum(subL[bg] + d + 1)bg = greturn retout = []for _ in range(Q):x, y, z = map(int, input().split())x -= 1out.append(get(x))add(x, y, z)print(*out, sep="\n")