結果
| 問題 | No.900 aδδitivee |
| ユーザー |
 rlangevin
|
| 提出日時 | 2024-01-18 12:26:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 770 ms / 2,000 ms |
| コード長 | 9,194 bytes |
| コンパイル時間 | 422 ms |
| コンパイル使用メモリ | 81,700 KB |
| 実行使用メモリ | 136,124 KB |
| 最終ジャッジ日時 | 2024-01-18 12:26:22 |
| 合計ジャッジ時間 | 20,518 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 38 ms
55,596 KB |
| testcase_01 | AC | 39 ms
55,596 KB |
| testcase_02 | AC | 48 ms
63,588 KB |
| testcase_03 | AC | 48 ms
63,624 KB |
| testcase_04 | AC | 49 ms
63,624 KB |
| testcase_05 | AC | 48 ms
63,592 KB |
| testcase_06 | AC | 49 ms
63,592 KB |
| testcase_07 | AC | 740 ms
135,724 KB |
| testcase_08 | AC | 736 ms
135,768 KB |
| testcase_09 | AC | 696 ms
135,716 KB |
| testcase_10 | AC | 735 ms
135,212 KB |
| testcase_11 | AC | 713 ms
135,476 KB |
| testcase_12 | AC | 736 ms
136,032 KB |
| testcase_13 | AC | 751 ms
135,676 KB |
| testcase_14 | AC | 710 ms
135,384 KB |
| testcase_15 | AC | 740 ms
136,124 KB |
| testcase_16 | AC | 710 ms
135,360 KB |
| testcase_17 | AC | 743 ms
135,832 KB |
| testcase_18 | AC | 751 ms
135,888 KB |
| testcase_19 | AC | 710 ms
135,704 KB |
| testcase_20 | AC | 733 ms
135,360 KB |
| testcase_21 | AC | 770 ms
135,816 KB |
| testcase_22 | AC | 525 ms
133,500 KB |
| testcase_23 | AC | 513 ms
133,384 KB |
| testcase_24 | AC | 552 ms
133,512 KB |
| testcase_25 | AC | 516 ms
133,492 KB |
| testcase_26 | AC | 534 ms
133,380 KB |
| testcase_27 | AC | 512 ms
133,372 KB |
| testcase_28 | AC | 550 ms
133,388 KB |
ソースコード
import sys
input = sys.stdin.readline
class SegmentTree:
def __init__(self,
n,
identity_e,
combine_f,
):
self._n = n
self._size = 1
while self._size < self._n:
self._size <<= 1
self._identity_e = identity_e
self._combine_f = combine_f
self._node = [self._identity_e] * (2 * self._size)
def build(self, array):
assert len(array) == self._n
for index, value in enumerate(array, start=self._size):
self._node[index] = value
for index in range(self._size - 1, 0, -1):
self._node[index] = self._combine_f(
self._node[index << 1 | 0],
self._node[index << 1 | 1]
)
def update(self, index, value):
i = self._size + index
self._node[i] = value
while i > 1:
i >>= 1
self._node[i] = self._combine_f(
self._node[i << 1 | 0],
self._node[i << 1 | 1]
)
def fold(self, L, R):
L += self._size
R += self._size
value_L = self._identity_e
value_R = self._identity_e
while L < R:
if L & 1:
value_L = self._combine_f(value_L, self._node[L])
L += 1
if R & 1:
R -= 1
value_R = self._combine_f(self._node[R], value_R)
L >>= 1
R >>= 1
return self._combine_f(value_L, value_R)
def get(self, p):
return self._node[p + self._size]
def max_right(self, l, f):
assert 0 <= l <= self._n
assert f(self._identity_e)
if l == self._n:
return self._n
l += self._size
sm = self._identity_e
while True:
while l % 2 == 0:
l >>= 1
if not f(self._combine_f(sm, self._node[l])):
while l < self._size:
l <<= 1
if f(self._combine_f(sm, self._node[l])):
sm = self._combine_f(sm, self._node[l])
l += 1
return l - self._size
sm = self._combine_f(sm, self._node[l])
l += 1
if l & -l == l:
break
return self._n
def min_left(self, r, f):
assert 0 <= r <= self._n
assert f(self._identity_e)
if r == 0:
return 0
r += self._size
sm = self._identity_e
while True:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not f(self._combine_f(self._node[r], sm)):
while r < self._size:
r = 2 * r + 1
if f(self._combine_f(self._node[r], sm)):
sm = self._combine_f(self._node[r], sm)
r -= 1
return r + 1 - self._size
sm = self._combine_f(self._node[r], sm)
if r & -r == r:
break
return 0
from operator import add
class EulerTour():
def __init__(self, N):
self.N = N
self._in = [0] * N
self._out = [0] * N
self.depth = [-1] * N
self.weight = [0] * N
self.par = [-1] * N
self.tour = [-1] * (2 * N)
self.G = [[] for i in range(N)]
def add_edge(self, u, v, w):
self.G[u].append((v, w))
self.G[v].append((u, w))
def build(self, root=0):
stack = [root]
self.depth[root] = 0
for i in range(2 * self.N):
s = stack.pop()
if s >= 0:
stack.append(~s)
self.tour[i] = s
self._in[s] = i
for u, w in self.G[s]:
if u == self.par[s]:
continue
self.par[u] = s
self.weight[u] = w
self.depth[u] = self.depth[s] + 1
stack.append(u)
else:
s = ~s
self._out[s] = i
self.tour[i] = ~s
def get_path(self, u, v):
d = self.elist.fold(0, self._in[u] + 1) + self.elist.fold(0, self._in[v] + 1)
lca = self.get_lca(u, v)
d -= 2 * self.elist.fold(0, self._in[lca] + 1)
return d
def update(self, u, v, w):
e = v
if self.par[u] == v:
e = u
self.elist.update(self._in[e], w)
self.elist.update(self._out[e], -w)
def get_lca(self, u, v):
if self._in[u] > self._in[v]:
u, v = v, u
lca = self.dlist.fold(self._in[u], self._in[v] + 1) % self.N
return lca
class LazySegmentTree:
def __init__(
self,
n,
identity_e_node,
identity_e_lazy,
combine_node_f,
combine_lazy_f,
reflect_f,
):
self._n = n
self._size = 1
self._height = 0
while self._size < self._n:
self._size <<= 1
self._height += 1
self._identity_e_node = identity_e_node
self._identity_e_lazy = identity_e_lazy
self._combine_node_f = combine_node_f
self._combine_lazy_f = combine_lazy_f
self._reflect_f = reflect_f
self._node = [self._identity_e_node] * (2 * self._size)
self._lazy = [self._identity_e_lazy] * (2 * self._size)
#遅延データの値を値データに反映させたときの値を返す。
def _reflect_lazy(self, index):
return self._reflect_f(self._node[index], self._lazy[index])
def _propagate_from_top(self, index):
index += self._size
for h in range(self._height, 0, -1):
i = index >> h
if self._lazy[i] != self._identity_e_lazy:
self._lazy[i << 1] = self._combine_lazy_f(
self._lazy[i << 1], self._lazy[i]
)
self._lazy[i << 1 | 1] = self._combine_lazy_f(
self._lazy[i << 1 | 1], self._lazy[i]
)
self._node[i] = self._reflect_lazy(i)
self._lazy[i] = self._identity_e_lazy
def _update_from_bottom(self, index):
index = (index + self._size) >> 1
while index:
self._node[index] = self._combine_node_f(
self._reflect_lazy(index << 1),
self._reflect_lazy(index << 1 | 1)
)
index >>= 1
def build(self, array):
assert len(array) == self._n
for index, value in enumerate(array, start=self._size):
self._node[index] = value
for index in range(self._size - 1, 0, -1):
self._node[index] = self._combine_node_f(
self._node[index << 1],
self._node[index << 1 | 1]
)
# 区間更新 位置[L, R) (0-indexed)を値valueで更新
def update(self, L, R, value):
self._propagate_from_top(L)
self._propagate_from_top(R - 1)
L_lazy = L + self._size
R_lazy = R + self._size
while L_lazy < R_lazy:
if L_lazy & 1:
self._lazy[L_lazy] = self._combine_lazy_f(self._lazy[L_lazy], value)
L_lazy += 1
if R_lazy & 1:
R_lazy -= 1
self._lazy[R_lazy] = self._combine_lazy_f(self._lazy[R_lazy], value)
L_lazy >>= 1
R_lazy >>= 1
self._update_from_bottom(L)
self._update_from_bottom(R - 1)
# 区間取得 区間[L, R) (0-indexed)内の要素について
# L番目から順にcombine_node_fを適用した値を返す。
def fold(self, L, R):
self._propagate_from_top(L)
self._propagate_from_top(R - 1)
L += self._size
R += self._size
value_L = self._identity_e_node
value_R = self._identity_e_node
while L < R:
if L & 1:
value_L = self._combine_node_f(value_L, self._reflect_lazy(L))
L += 1
if R & 1:
R -= 1
value_R = self._combine_node_f(self._reflect_lazy(R), value_R)
L >>= 1
R >>= 1
return self._combine_node_f(value_L, value_R)
# 区間加算する場合
def op(x1, x2):
v1, s1 = x1
v2, s2 = x2
return (v1 + v2, s1 + s2)
def reflect(node, lazy):
return (node[0] + lazy * node[1], node[1])
N = int(input())
T = EulerTour(N)
for i in range(N - 1):
a, b, w = map(int, input().split())
T.add_edge(a, b, w)
T.build(0)
_in, _out, tour, w = T._in, T._out, T.tour, T.weight
LT = LazySegmentTree(
2 * N,
(0, 0),
0,
op,
add,
reflect
)
L = [(0, 1)]
for i in range(1, 2 * N - 1):
if tour[i] >= 0:
L.append((w[tour[i]], 1))
else:
L.append((-w[~tour[i]], -1))
L.append((0, -1))
LT.build(L)
Q = int(input())
for i in range(Q):
q = list(map(int, input().split()))
if q[0] == 1:
a, x = q[1:]
LT.update(_in[a]+1, _out[a], x)
else:
b = q[1]
print(LT.fold(0, _in[b] + 1)[0])