結果
| 問題 |
No.2470 Gemini Tree(Ver.Jadeite)
|
| コンテスト | |
| ユーザー |
👑  SPD_9X2
|
| 提出日時 | 2023-07-29 04:41:07 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,745 ms / 5,000 ms |
| コード長 | 7,322 bytes |
| コンパイル時間 | 544 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 188,268 KB |
| 最終ジャッジ日時 | 2024-11-08 11:17:15 |
| 合計ジャッジ時間 | 61,389 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
"""
Gemini Tree Ver.Jade (3) 想定解
実装方針:
DFSを行う。
この時に計算するのは・・・
・辺のDFS順
・E_cutに含まれる辺の列挙
・各子部分木に含まれている 緑/青の 石の個数
・ラベル (最後に通った E_cut の辺)
"""
import sys
from sys import stdin
def segfunc(x,y):
return min(x,y)
class LazySegTree_RAQ:
def __init__(self,init_val,segfunc,ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1<<(n-1).bit_length()
self.tree = [ide_ele]*2*self.num
self.lazy = [0]*2*self.num
for i in range(n):
self.tree[self.num+i] = init_val[i]
for i in range(self.num-1,0,-1):
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
def gindex(self,l,r):
l += self.num
r += self.num
lm = l>>(l&-l).bit_length()
rm = r>>(r&-r).bit_length()
while r>l:
if l<=lm:
yield l
if r<=rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagates(self,*ids):
for i in reversed(ids):
v = self.lazy[i]
if v==0:
continue
self.lazy[i] = 0
self.lazy[2*i] += v
self.lazy[2*i+1] += v
self.tree[2*i] += v
self.tree[2*i+1] += v
def add(self,l,r,x):
ids = self.gindex(l,r)
l += self.num
r += self.num
while l<r:
if l&1:
self.lazy[l] += x
self.tree[l] += x
l += 1
if r&1:
self.lazy[r-1] += x
self.tree[r-1] += x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1]) + self.lazy[i]
def query(self,l,r):
self.propagates(*self.gindex(l,r))
res = self.ide_ele
l += self.num
r += self.num
while l<r:
if l&1:
res = self.segfunc(res,self.tree[l])
l += 1
if r&1:
res = self.segfunc(res,self.tree[r-1])
l >>= 1
r >>= 1
return res
N = int(stdin.readline())
s = list(stdin.readline()[:-1])
lis = [ [] for i in range(N) ]
elis = []
for i in range(N-1):
u,v,w = map(int,stdin.readline().split())
u -= 1
v -= 1
lis[u].append( (v,i) )
lis[v].append( (u,i) )
elis.append( (u,v,w) )
# G < B にする
g_all = 0
b_all = 0
for c in s:
if c == "G":
g_all += 1
else:
b_all += 1
if g_all > b_all:
for i in range(N):
if s[i] == "G":
s[i] = "B"
else:
s[i] = "G"
g_all,b_all = b_all,g_all
# dfs
stk = [0] #スタック
serched_edge_num = [0] * N #頂点vから出る何番目の辺まで処理したか
is_serched = [False] * N
elis_dfs = [] #dfs順に並んだ辺のリスト(in,out で2回記録)
visit_edge = [None] * N #どの辺で訪問したか？
gnum_child = [0] * N #各子部分木に含まれる緑の石の個数
bnum_child = [0] * N
while stk:
v = stk[-1]
if serched_edge_num[v] == 0: #最初に頂点を訪問した際の処理
is_serched[v] = True
if s[v] == "G":
gnum_child[v] += 1
else:
bnum_child[v] += 1
if serched_edge_num[v] == len(lis[v]): #頂点を去る場合の処理
if len(stk) >= 2: #親がいる場合
p = stk[-2] #親
# gnum,bnumを更新
gnum_child[p] += gnum_child[v]
bnum_child[p] += bnum_child[v]
# visit edgeを elis_dfsに加える, 1,2項目は親,子の順, 3項目はeidx , 4項目はin/out
elis_dfs.append( ( p , v , visit_edge[v] , False) )
stk.pop()
else: #探索すべき辺が残っている場合の処理
nexv,eidx = lis[v][serched_edge_num[v]]
serched_edge_num[v] += 1
# print (nexv,eidx)
if is_serched[nexv]: #親なら飛ばす
pass
else:
stk.append(nexv)
elis_dfs.append( (v,nexv,eidx,True) )
visit_edge[nexv] = eidx
# print (elis_dfs)
# print (gnum_child)
# print (bnum_child)
# オイラーツアー順に見て、ラベルを付ける
label = [None] * N
label_stk = []
for p,c,eidx,is_in in elis_dfs:
if gnum_child[c]+bnum_child[c] == b_all: #初期地点がラベル付きだったときの対策
if is_in:
for p2,c2,_,_ in elis_dfs:
label[p2] = eidx
if c == c2:
break
label[c2] = eidx
for p2,c2,_,_ in reversed(elis_dfs):
label[p2] = eidx
if c == c2:
break
label[c2] = eidx
elif gnum_child[c] + bnum_child[c] == g_all: #子部分木のサイズがGの時
if is_in:
label_stk.append(eidx)
label[c] = eidx
else:
label_stk.pop()
else:
if label_stk:
label[p] = label[c] = label_stk[-1]
# print (label)
# eidx -> elis_dfsの該当位置2箇所 を参照できるようにしておく
ref_eidx2ed = [ [None,None] for i in range(N-1) ]
for i in range(len(elis_dfs)):
p,c,eidx,is_in = elis_dfs[i]
if is_in:
ref_eidx2ed[eidx][0] = i
else:
ref_eidx2ed[eidx][1] = i
# cutできる辺だけ0にしておく
first_seg_state = [float("inf")] * (2*N-2)
for i,(p,c,eidx,is_in) in enumerate(elis_dfs):
if is_in and (gnum_child[c]+bnum_child[c] in (b_all,g_all)):
first_seg_state[i] = 0
# セグ木の宣言 (区間加算/区間最小値)
seg = LazySegTree_RAQ( first_seg_state , segfunc , float("inf") )
# クエリの処理
Q = int(stdin.readline())
ANS = []
if g_all == 0:
for i in range(Q):
print (0)
sys.exit()
for loop in range((N-1) + Q):
if loop < N-1: #初期状態もクエリとして処理
eidx,a = loop,elis[loop][2]
else:
eidx,a = map(int,stdin.readline().split())
eidx -= 1
lidx,ridx = ref_eidx2ed[eidx] #セグ木における区間
p,c,_,_ = elis_dfs[lidx] #今回伸ばす辺の2頂点
if label[p] == label[c] == None: # どちらにもラベルなし
seg.add(lidx,ridx,a*(g_all-gnum_child[c]))
if lidx > 0:
seg.add(0,lidx,a*gnum_child[c])
if ridx < 2*N-2:
seg.add(ridx,2*N-2,a*gnum_child[c])
else:
if (gnum_child[c] + bnum_child[c]) * 2 < N:
g_min_side = gnum_child[c]
b_min_side = bnum_child[c]
else:
g_min_side = g_all - gnum_child[c]
b_min_side = b_all - bnum_child[c]
nlabel = label[p] if label[p] != None else label[c]
nlabel_idx = ref_eidx2ed[nlabel][0]
seg.add(0,2*N-2,a*g_min_side)
seg.add(nlabel_idx,nlabel_idx+1, a*(b_min_side-g_min_side) )
# クエリだったらANS配列に加える
if loop >= N-1:
ans = seg.query(0,2*N-2)
ANS.append(ans)
# print ( p,c,label[p],label[c], [seg.query(i,i+1) for i in range(2*N-2) ] )
print (*ANS,sep="\n")