結果
| 問題 |
No.2470 Gemini Tree(Ver.Jadeite)
|
| コンテスト | |
| ユーザー |
 rin204
|
| 提出日時 | 2023-07-30 17:36:57 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,780 ms / 5,000 ms |
| コード長 | 11,908 bytes |
| コンパイル時間 | 514 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 144,640 KB |
| 最終ジャッジ日時 | 2024-11-08 11:18:07 |
| 合計ジャッジ時間 | 43,971 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
class HLD:
def __init__(self, n, edges=None):
self.n = n
if edges is None:
self.edges = [[] for _ in range(n)]
else:
self.edges = edges
# コピーしてないので注意
self.size = [-1] * n
self.par = [-1] * n
self.depth = [-1] * n
self.path_ind = [-1] * n
self.path_root = []
self.heavy_child = [-1] * n
self.isheavy = [False] * n
self.L = [-1] * n
self.R = [-1] * n
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, root=0):
self.depth[root] = 0
st = [root]
route = [root]
while st:
pos = st.pop()
for npos in self.edges[pos]:
if self.depth[npos] == -1:
self.depth[npos] = self.depth[pos] + 1
self.par[npos] = pos
st.append(npos)
route.append(npos)
for pos in route[::-1]:
self.size[pos] = 1
ma = -1
for npos in self.edges[pos]:
if self.size[npos] != -1:
self.size[pos] += self.size[npos]
if self.size[npos] > ma:
ma = self.size[npos]
self.heavy_child[pos] = npos
if ma != -1:
self.isheavy[self.heavy_child[pos]] = True
self.isheavy[root] = True
path = 0
st = [~root, root]
self.path_root = [root]
cc = 0
while st:
pos = st.pop()
if pos >= 0:
self.L[pos] = cc
cc += 1
if not self.isheavy[pos]:
path += 1
self.path_root.append(pos)
self.path_ind[pos] = path
for npos in self.edges[pos]:
if npos == self.par[pos] or npos == self.heavy_child[pos]:
continue
st.append(~npos)
st.append(npos)
if self.heavy_child[pos] != -1:
npos = self.heavy_child[pos]
st.append(~npos)
st.append(npos)
else:
self.R[~pos] = cc
def get_path(self, u, v):
ll = [u]
rr = [v]
while self.path_ind[u] != self.path_ind[v]:
if (
self.depth[self.path_root[self.path_ind[u]]]
>= self.depth[self.path_root[self.path_ind[v]]]
):
u = self.path_root[self.path_ind[u]]
ll.append(u)
u = self.par[u]
ll.append(u)
else:
v = self.path_root[self.path_ind[v]]
rr.append(v)
v = self.par[v]
rr.append(v)
ll += rr[::-1]
res = []
for i in range(0, len(ll), 2):
res.append((ll[i], ll[i + 1]))
return res
def lca(self, u, v):
while self.path_ind[u] != self.path_ind[v]:
if (
self.depth[self.path_root[self.path_ind[u]]]
>= self.depth[self.path_root[self.path_ind[v]]]
):
u = self.par[self.path_root[self.path_ind[u]]]
else:
v = self.par[self.path_root[self.path_ind[v]]]
if self.depth[u] >= self.depth[v]:
return v
else:
return u
def dist(self, u, v):
return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]
def reorder(self, A, rev=False):
ret = [0] * self.n
for i in range(self.n):
ret[self.L[i]] = A[i]
if rev:
ret = ret[::-1]
return ret
class LazySegmentTreeBase_:
def ope(self, l, r):
return None
def e(self):
return None
def mapping(self, f, x):
return None
def composition(self, f, g):
return None
def id_(self):
return None
def __init__(self, n, init=None):
self.n = n
self.log = (n - 1).bit_length()
self.n0 = 1 << self.log
self.data = [self.e()] * (2 * self.n0)
self.lazy = [self.id_()] * self.n0
if init is not None:
for i in range(n):
self.data[self.n0 + i] = init[i]
for i in range(self.n0 - 1, 0, -1):
self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])
def _all_apply(self, p, f):
self.data[p] = self.mapping(f, self.data[p])
if p < self.n0:
self.lazy[p] = self.composition(f, self.lazy[p])
def _push(self, p):
self._all_apply(2 * p, self.lazy[p])
self._all_apply(2 * p + 1, self.lazy[p])
self.lazy[p] = self.id_()
def _update(self, p):
self.data[p] = self.ope(self.data[2 * p], self.data[2 * p + 1])
def set(self, p, x):
p += self.n0
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 __setitem__(self, p, x):
self.set(p, x)
def get(self, p):
p += self.n0
for i in range(self.log, 0, -1):
self._push(p >> i)
return self.data[p]
def __getitem__(self, p):
return self.get(p)
def prod(self, l, r):
assert 0 <= l <= r <= self.n0
l += self.n0
r += self.n0
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)
lles = self.e()
rres = self.e()
while l < r:
if l & 1:
lles = self.ope(lles, self.data[l])
l += 1
if r & 1:
r -= 1
rres = self.ope(self.data[r], rres)
l >>= 1
r >>= 1
return self.ope(lles, rres)
def all_prod(self):
return self.data[1]
def _apply(self, p, f):
p += self.n0
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=None):
if f is None:
self._apply(l, r)
return
if l == r:
return
l += self.n0
r += self.n0
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 = l
r2 = 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 = l2
r = 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, f):
if l == self.n:
return self.n
l += self.n0
for i in range(self.log, 0, -1):
self._push(l >> i)
sm = self.e()
while 1:
while l % 2 == 0:
l >>= 1
if not f(self.ope(sm, self.data[l])):
while l < self.n0:
self._push(l)
l <<= 1
if f(self.ope(sm, self.data[l])):
sm = self.ope(sm, self.data[l])
l += 1
return l - self.n0
sm = self.ope(sm, self.data[l])
l += 1
if l & -l == l:
break
return self.n
def min_left(self, r, f):
if r == 0:
return 0
r += self.n0
for i in range(self.log, 0, -1):
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
sm = self.e()
while 1:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not f(self.ope(self.data[r], sm)):
while r < self.n0:
self._push(r)
r = 2 * r + 1
if f(self.ope(self.data[r], sm)):
sm = self.ope(self.data[r], sm)
r -= 1
return r + 1 - self.n0
sm = self.ope(self.data[r], sm)
if r & -r == r:
break
return 0
inf = 1 << 60
class lseg(LazySegmentTreeBase_):
def ope(self, l, r):
return min(l, r)
def e(self):
return inf
def mapping(self, f, x):
return f + x
def composition(self, f, g):
return f + g
def id_(self):
return 0
n = int(input())
S = list(input())
g = S.count("G")
b = S.count("B")
if g > b:
g, b = b, g
gb = {"G": "B", "B": "G"}
S = [gb[s] for s in S]
if g == 0:
for _ in range(n - 1):
input()
for _ in range(int(input())):
input()
print(0)
exit()
E = [list(map(int, input().split())) for _ in range(n - 1)]
edges = [[] for _ in range(n)]
for i in range(n - 1):
E[i][0] -= 1
E[i][1] -= 1
edges[E[i][0]].append((E[i][1], E[i][2]))
edges[E[i][1]].append((E[i][0], E[i][2]))
cent = -1
siz = [0] * n
gc = [0] * n
cent = -1
def dfs(pos):
global cent
st = [pos]
route = []
used = [False] * n
used[pos] = True
while st:
pos = st.pop()
route.append(pos)
for npos, _ in edges[pos]:
if used[npos]:
continue
used[npos] = True
st.append(npos)
for pos in route[::-1]:
siz[pos] = 1
gc[pos] = 0
if S[pos] == "G":
gc[pos] = 1
ok = True
for npos, _ in edges[pos]:
if not used[npos]:
siz[pos] += siz[npos]
gc[pos] += gc[npos]
if siz[npos] * 2 > n:
ok = False
used[pos] = False
if 2 * (n - siz[pos]) <= n and ok:
cent = pos
dfs(0)
hld = HLD(n)
for u, v, _ in E:
hld.add_edge(u, v)
hld.build(cent)
cc = cent
dfs(cent)
cent = cc
ini = [0] * n
for i in range(n):
if siz[i] != g:
ini[hld.L[i]] = inf
seg = lseg(n, ini)
upp = [-1] * n
st = [cent]
upp[cent] = cent
while st:
pos = st.pop()
for npos, _ in edges[pos]:
if upp[npos] == -1:
upp[npos] = upp[pos]
if siz[pos] > g:
upp[npos] = npos
st.append(npos)
def add(u, v, w):
if hld.depth[u] < hld.depth[v]:
u, v = v, u
x = w * gc[u]
seg.apply(0, n, x)
x *= -1
x += w * min(g - gc[u], siz[u] - gc[u])
u = upp[u]
seg.apply(hld.L[u], hld.R[u], x)
for u, v, w in E:
add(u, v, w)
for _ in range(int(input())):
e, a = map(int, input().split())
e -= 1
add(E[e][0], E[e][1], a)
print(seg.all_prod())