結果
問題 | No.1038 TreeAddQuery |
ユーザー |
👑 |
提出日時 | 2023-07-08 14:07:42 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,333 bytes |
コンパイル時間 | 560 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 199,316 KB |
最終ジャッジ日時 | 2024-07-22 09:36:25 |
合計ジャッジ時間 | 29,258 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 TLE * 2 |
ソースコード
import osimport sysfrom io import BytesIO, IOBaseBUFSIZE = 8192class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)def input():return sys.stdin.readline().rstrip("\r\n")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)