結果

問題 No.2470 Gemini Tree(Ver.Jadeite)
ユーザー 👑 SPD_9X2SPD_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
53,632 KB
testcase_01 AC 40 ms
53,504 KB
testcase_02 AC 41 ms
53,504 KB
testcase_03 AC 45 ms
53,632 KB
testcase_04 AC 44 ms
53,248 KB
testcase_05 AC 45 ms
53,120 KB
testcase_06 AC 2,386 ms
178,356 KB
testcase_07 AC 2,436 ms
181,744 KB
testcase_08 AC 2,553 ms
179,516 KB
testcase_09 AC 2,583 ms
180,196 KB
testcase_10 AC 2,611 ms
182,832 KB
testcase_11 AC 2,630 ms
180,380 KB
testcase_12 AC 2,540 ms
180,576 KB
testcase_13 AC 2,565 ms
181,204 KB
testcase_14 AC 2,745 ms
182,868 KB
testcase_15 AC 2,358 ms
181,328 KB
testcase_16 AC 2,277 ms
181,072 KB
testcase_17 AC 2,371 ms
188,268 KB
testcase_18 AC 2,265 ms
179,240 KB
testcase_19 AC 2,220 ms
178,584 KB
testcase_20 AC 2,206 ms
178,864 KB
testcase_21 AC 1,932 ms
177,948 KB
testcase_22 AC 2,344 ms
181,424 KB
testcase_23 AC 2,253 ms
181,016 KB
testcase_24 AC 2,207 ms
176,720 KB
testcase_25 AC 2,402 ms
180,288 KB
testcase_26 AC 2,215 ms
178,912 KB
testcase_27 AC 2,431 ms
179,412 KB
testcase_28 AC 2,295 ms
180,812 KB
testcase_29 AC 2,479 ms
181,672 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

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")
0