結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
👑  rin204
|
| 提出日時 | 2022-07-12 15:07:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 9,130 ms / 10,000 ms |
| コード長 | 9,183 bytes |
| コンパイル時間 | 324 ms |
| コンパイル使用メモリ | 87,312 KB |
| 実行使用メモリ | 277,752 KB |
| 最終ジャッジ日時 | 2023-09-05 17:11:06 |
| 合計ジャッジ時間 | 34,621 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 9,130 ms
277,752 KB |
| testcase_01 | AC | 5,584 ms
269,384 KB |
| testcase_02 | AC | 7,862 ms
276,204 KB |
ソースコード
MOD = 10 ** 9 + 7
class lazy_segtree():
def __init__(self, lst, ope, e, mapping, composition, id_):
self.n = len(lst)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.data = [e for _ in range(2 * self.size)]
self.lz = [id_ for _ in range(self.size)]
self.e = e
self.op = ope
self.mapping = mapping
self.composition = composition
self.identity = id_
for i in range(self.n):
self.data[self.size + i] = lst[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def update(self, k):
self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])
def all_apply(self, k, f):
self.data[k] = self.mapping(f, self.data[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2 * k, self.lz[k])
self.all_apply(2 * k + 1, self.lz[k])
self.lz[k] = self.identity
def set(self, p, x):
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.data[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.data[p]
def prod(self, l, r):
if l == r: return self.e
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if (l >> i) << i != l:
self.push(l >> i)
if (r >> i) << i != r:
self.push(r >> i)
sml, smr = self.e, self.e
while l < r:
if l & 1:
sml = self.op(sml, self.data[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.data[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.data[1]
def apply_point(self, p, f):
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.data[p] = self.mapping(f, self.data[p])
for i in range(1, self.log + 1):
self.update(p >> i)
def apply(self, l, r, f):
if l == r: return
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if (l >> i) << i != l:
self.push(l >> i)
if (r >> i) << i != r:
self.push((r - 1) >> i)
l2, r2 = l, r
while l < r:
if l & 1:
self.all_apply(l, f)
l += 1
if r & 1:
r -= 1
self.all_apply(r, f)
l >>= 1
r >>= 1
l, r = l2, r2
for i in range(1, self.log + 1):
if (l >> i) << i != l:
self.update(l >> i)
if (r >> i) << i != r:
self.update((r - 1) >> i)
def max_right(self, l, g):
if l == self.n: return self.n
l += self.size
for i in range(self.log, 0, -1):
self.push(l >> i)
sm = self.e
while 1:
while i % 2 == 0:
l >>= 1
if not g(self.op(sm, self.data[l])):
while l < self.size:
self.push(l)
l *= 2
if g(self.op(sm, self.data[l])):
sm = self.op(sm, self.data[l])
l += 1
return l - self.size
sm = self.op(sm, self.data[l])
l += 1
if l & -l == l:
break
return self.n
def min_left(self, r, g):
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r - 1) >> i)
sm = self.e
while 1:
r -= 1
while r > 1 and r % 2 == 1:
r >>= 1
if not g(self.op(self.data[r], sm)):
while r < self.size:
self.push(r)
r = 2 * r + 1
if g(self.op(self.data[r], sm)):
sm = self.op(self.data[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.data[r], sm)
if r & -r == r:
break
return 0
class HLD:
def __init__(self, n, edges=None, P=None, root=0):
self.n = n
self.edges = [[] for _ in range(n)]
self.parent = [-1] * n
if edges is not None:
stack = [(root, -1)]
while stack:
pos, bpos = stack.pop()
for npos in edges[pos]:
if bpos == npos:
continue
self.edges[pos].append(npos)
self.parent[npos] = pos
stack.append((npos, pos))
else:
for i, p in enumerate(P):
if p != -1:
self.edges[p].append(i)
self.dist = [-1] * n
size = [1] * n
self.dist[root] = 0
stack = [(root, 1), (root, 0)]
while stack:
pos, t = stack.pop()
if t == 0:
for npos in self.edges[pos]:
self.dist[npos] = self.dist[pos] + 1
stack.append((npos, 1))
stack.append((npos, 0))
else:
for npos in self.edges[pos]:
size[pos] += size[npos]
self.index = [-1] * n
self.path = [-1] * n
ind = 0
bd = -1
pathid = 0
stack = [root]
self.parent_path = [-1] * n
self.dist_path = [0] * n
self.top_path = [root] * n
while stack:
pos = stack.pop()
self.index[pos] = ind
ind += 1
if self.dist[pos] <= bd:
self.parent_path[pathid + 1] = self.parent[pos]
pathid += 1
self.dist_path[pathid] = self.dist[pos]
self.top_path[pathid] = pos
self.path[pos] = pathid
bd = self.dist[pos]
self.edges[pos].sort(key = lambda x:size[x])
for npos in self.edges[pos]:
stack.append(npos)
del self.parent_path[pathid + 1:]
del self.dist_path[pathid + 1:]
del self.top_path[pathid + 1:]
def seg(self, lst, ope, e, mapping, composition, id_):
self.e = e
self.ope = ope
A = [None] * self.n
for i in range(self.n):
A[self.index[i]] = lst[i]
self.tree = lazy_segtree(A, ope, e, mapping, composition, id_)
def add(self, l, r, x):
while self.path[l] != self.path[r]:
if self.dist_path[self.path[l]] >= self.dist_path[self.path[r]]:
top = self.top_path[self.path[l]]
self.tree.apply(self.index[top], self.index[l] + 1, x)
l = self.parent_path[self.path[l]]
else:
top = self.top_path[self.path[r]]
self.tree.apply(self.index[top], self.index[r] + 1, x)
r = self.parent_path[self.path[r]]
if self.dist[l] <= self.dist[r]:
self.tree.apply(self.index[l], self.index[r] + 1, x)
else:
self.tree.apply(self.index[r], self.index[l] + 1, x)
def query(self, l, r):
lhs = self.e
rhs = self.e
while self.path[l] != self.path[r]:
if self.dist_path[self.path[l]] >= self.dist_path[self.path[r]]:
top = self.top_path[self.path[l]]
lhs = self.ope(lhs, self.tree.prod(self.index[top], self.index[l] + 1))
l = self.parent_path[self.path[l]]
else:
top = self.top_path[self.path[r]]
rhs = self.ope(self.tree.prod(self.index[top], self.index[r] + 1), rhs)
r = self.parent_path[self.path[r]]
if self.dist[l] <= self.dist[r]:
lhs = self.ope(lhs, self.tree.prod(self.index[l], self.index[r] + 1))
else:
rhs = self.ope(self.tree.prod(self.index[r], self.index[l] + 1), rhs)
return self.ope(lhs, rhs)
n = int(input())
S = list(map(int, input().split()))
C = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
edges[u].append(v)
edges[v].append(u)
hld = HLD(n, edges=edges)
e = (0, 0)
def ope(l, r):
return ((l[0] + r[0]) % MOD, (l[1] + r[1]) % MOD)
def mapping(x, l):
return (l[0], (l[0] * x + l[1]) % MOD)
def composition(x, y):
return x + y
id_ = 0
hld.seg([(c, s) for c, s in zip(C, S)], ope, e, mapping, composition, id_)
for _ in range(int(input())):
query = list(map(int, input().split()))
if query[0] == 0:
x, y, z = query[1:]
hld.add(x - 1, y - 1, z)
else:
x, y = query[1:]
ans = hld.query(x - 1, y - 1)
print(ans[1])