結果

問題 No.1038 TreeAddQuery
ユーザー 👑 rin204
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class CentroidDecomposition:
def __init__(self, n, edges=None):
self.n = n
self.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 -= indexed
v -= indexed
self.add_edge(u, v)
def build(self):
stack = [(0, -1, 0, -1)]
while stack:
pos, bpos, d, c = stack.pop()
st = [pos]
route = []
sz = 0
if 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] = 1
while st:
pos = st.pop()
if bpos != -1:
self.pars[pos].append(bpos)
self.depth[pos] = -2
route.append(pos)
sz += 1
if d >= 1:
self.treeind[d - 1][pos] = c
for 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] + 1
g = -1
while route:
pos = route.pop()
self.size[pos] = 1
self.depth[pos] = -1
isg = True
for npos in self.edges[pos]:
if self.depth[npos] == -1:
self.size[pos] += self.size[npos]
if self.size[npos] * 2 > sz:
isg = False
break
if isg and 2 * self.size[pos] >= sz:
g = pos
if len(self.centroids) == d:
self.centroids.append([])
self.centroids[d].append(g)
self.size[g] = sz
self.par[g] = bpos
self.depth[g] = d
self.cent_dist[d][g] = 0
if sz != 1:
c = 0
for npos in self.edges[g]:
if self.depth[npos] == -1:
stack.append((npos, g, d + 1, c))
c += 1
self.childcnt[g] = c
def 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 ret
class BIT:
def __init__(self, n):
self.n = n
self.data = [0] * (n + 1)
if n == 0:
self.n0 = 0
else:
self.n0 = 1 << (n.bit_length() - 1)
def sum_(self, i):
s = 0
while i > 0:
s += self.data[i]
i -= i & -i
return s
def 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 += 1
while i <= self.n:
self.data[i] += x
i += i & -i
def lower_bound(self, x):
if x <= 0:
return 0
i = 0
k = self.n0
while k > 0:
if i + k <= self.n and self.data[i + k] < x:
x -= self.data[i + k]
i += k
k //= 2
return i + 1
n, 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] * n
subL = [0] * n
for d in range(logn):
c = 0
c2 = 0
for g in G.centroids[d]:
L[g] = c
if d != 0:
subL[g] = c2
c += G.size[g]
c2 += G.size[g] + 1
def add(x, y, z):
bg = -1
for g, j, d in G.cent_ind_dist(x):
dd = y - d
if 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 = g
def get(x):
bg = -1
ret = 0
for 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 = g
return ret
for _ in range(Q):
x, y, z = map(int, input().split())
x -= 1
print(get(x))
add(x, y, z)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0