結果
問題 | No.1038 TreeAddQuery |
ユーザー |
👑 |
提出日時 | 2023-07-08 14:04:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,617 bytes |
コンパイル時間 | 386 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 200,808 KB |
最終ジャッジ日時 | 2024-07-22 09:32:59 |
合計ジャッジ時間 | 18,825 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 13 |
ソースコード
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.pars = [[] for _ in range(n)] # pars[i][j] := 頂点 i の先祖の内,深さが j であるものself.centroids = [] # centroids[i] := 深さが i の重心のリストself.treeind = [] # treeind[i][j] := 頂点 j が深さ i の重心の何番目の部分木かself.cent_dist = [] # cent_dist[i][j] := 頂点 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.treeind.append([-1] * self.n)self.cent_dist.append([-1] * self.n)if d >= 1:self.cent_dist[d - 1][pos] = 1while st:pos = st.pop()if bpos != -1:self.pars[pos].append(bpos)self.depth[pos] = -2route.append(pos)sz += 1if d >= 1:self.treeind[d - 1][pos] = cfor npos in self.edges[pos]:if self.depth[npos] == -1:st.append(npos)if d >= 1:self.cent_dist[d - 1][npos] = self.cent_dist[d - 1][pos] + 1g = -1while route:pos = route.pop()self.size[pos] = 1self.depth[pos] = -1isg = 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 = posif len(self.centroids) == d:self.centroids.append([])self.centroids[d].append(g)self.size[g] = szself.par[g] = bposself.depth[g] = dself.cent_dist[d][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] = cdef cent_ind_dist(self, u):"""u + u の各先祖の {頂点番号,何番目の部分木か,距離} を返す"""ret = [(u, -1, 0)]for d in range(len(self.pars[u]) - 1, -1, -1):ret.append((self.pars[u][d], self.treeind[d][u], self.cent_dist[d][u]))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 + 1n, 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, j, 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 j != -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, j, d in G.cent_ind_dist(x):ret += bit[G.depth[g]].sum(L[g] + d + 1)if j != -1:ret -= subbit[G.depth[g]].sum(subL[bg] + d + 1)bg = greturn retfor _ in range(Q):x, y, z = map(int, input().split())x -= 1print(get(x))add(x, y, z)