結果
問題 | No.1038 TreeAddQuery |
ユーザー |
👑 |
提出日時 | 2023-07-08 15:05:15 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,181 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 249,136 KB |
最終ジャッジ日時 | 2024-07-22 10:32:27 |
合計ジャッジ時間 | 51,541 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 TLE * 1 |
ソースコード
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 = nex, self.cent_distfor i in range(self.n):for j in range(self.logn):nex[i * self.logn + j] = self.treeind[j * self.n + i]self.treeind = nexdef cent_ind_dist(self, u):"""u + u の各先祖の {頂点番号, 距離} を返す"""ret = [(u, 0)]v = up = u * self.logn + self.depth[u] - 1for d in range(self.depth[u] - 1, -1, -1):v = self.par[v]ret.append((v, self.cent_dist[p]))p -= 1return 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 = []subbit = []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] + 1bit.append(BIT(c))if d != 0:subbit.append(BIT(c2))def 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):if G.size[g] >= d + 1:ret += bit[G.depth[g]].sum(L[g] + d + 1)if bg != -1 and G.size[bg] + 1 >= d + 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")