結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 47 ms
53,376 KB |
| testcase_01 | AC | 45 ms
53,248 KB |
| testcase_02 | AC | 45 ms
52,864 KB |
| testcase_03 | AC | 276 ms
80,704 KB |
| testcase_04 | AC | 299 ms
82,172 KB |
| testcase_05 | AC | 280 ms
81,040 KB |
| testcase_06 | AC | 269 ms
82,192 KB |
| testcase_07 | AC | 288 ms
81,164 KB |
| testcase_08 | AC | 3,263 ms
182,000 KB |
| testcase_09 | AC | 3,576 ms
187,488 KB |
| testcase_10 | AC | 3,651 ms
187,300 KB |
| testcase_11 | AC | 3,682 ms
187,112 KB |
| testcase_12 | AC | 3,769 ms
188,176 KB |
| testcase_13 | TLE | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
ソースコード
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)