結果

問題 No.900 aδδitivee
ユーザー onakasuitacityonakasuitacity
提出日時 2019-10-12 11:52:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 881 ms / 2,000 ms
コード長 4,526 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 177,536 KB
最終ジャッジ日時 2024-11-27 15:06:58
合計ジャッジ時間 20,975 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,504 KB
testcase_01 AC 41 ms
52,608 KB
testcase_02 AC 46 ms
60,032 KB
testcase_03 AC 45 ms
60,032 KB
testcase_04 AC 45 ms
60,160 KB
testcase_05 AC 46 ms
60,160 KB
testcase_06 AC 48 ms
60,032 KB
testcase_07 AC 848 ms
138,368 KB
testcase_08 AC 868 ms
137,600 KB
testcase_09 AC 851 ms
136,448 KB
testcase_10 AC 875 ms
136,448 KB
testcase_11 AC 848 ms
136,448 KB
testcase_12 AC 845 ms
135,552 KB
testcase_13 AC 840 ms
136,064 KB
testcase_14 AC 850 ms
135,168 KB
testcase_15 AC 840 ms
135,552 KB
testcase_16 AC 849 ms
137,600 KB
testcase_17 AC 881 ms
137,088 KB
testcase_18 AC 849 ms
137,344 KB
testcase_19 AC 875 ms
137,216 KB
testcase_20 AC 868 ms
138,368 KB
testcase_21 AC 876 ms
136,064 KB
testcase_22 AC 805 ms
176,256 KB
testcase_23 AC 789 ms
175,872 KB
testcase_24 AC 826 ms
176,384 KB
testcase_25 AC 831 ms
177,536 KB
testcase_26 AC 814 ms
177,024 KB
testcase_27 AC 828 ms
176,796 KB
testcase_28 AC 794 ms
176,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree(object):
    def __init__(self,A,dot,e,comp,id,act):
        """
        A: array of monoid (M,dot,e)
        comp: composite function of Hom(M), comp(f,g)=gf
        id: identity map of M
        act: action on (Hom(M),M), act(f,a)=f(a)
        """
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__comp=comp
        self.__id=id
        self.__act=act
        self.__node=[e]*(2*n)
        self.__lazy=[id]*(2*n)
        for i in range(len(A)):
            self.__node[i+n]=A[i]
        for i in range(n-1,0,-1):
            self.__node[i]=self.__dot(self.__node[2*i],self.__node[2*i+1])

    def __propagate(self,i):
        if(self.__lazy[i]==self.__id): return
        node=self.__node
        lazy=self.__lazy
        if(i<self.__n): # propagate to children
            lazy[2*i]=self.__comp(lazy[2*i],lazy[i])
            lazy[2*i+1]=self.__comp(lazy[2*i+1],lazy[i])
        node[i]=self.__act(lazy[i],node[i]) # action
        lazy[i]=self.__id

    def __ancestors_propagate(self,i):
        if(i==1): return
        i//=2
        self.__ancestors_propagate(i)
        self.__propagate(i)

    def __update_ancestors(self,i):
        while(i!=1):
            self.__propagate(i+1-2*(i%2)) # propagate the sibling of i
            i//=2
            self.__node[i]=self.__dot(self.__node[2*i],self.__node[2*i+1])

    def update(self,i,c):
        i+=self.__n
        self.__ancestors_propagate(i)
        self.__propagate(i)
        self.__node[i]=c
        self.__update_ancestors(i)

    def add(self,l,r,f):
        range,low=[],[0]*2
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                if(low[0]==0): low[0]=l
                range.append(l)
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                range.append(r)
                if(low[1]==0): low[1]=r
            r//=2
        for i in low:
            if(i): self.__ancestors_propagate(i)
        for i in range: self.__lazy[i]=self.__comp(self.__lazy[i],f)
        for i in low:
            if(i):
                self.__propagate(i)
                self.__update_ancestors(i)

    def sum(self,l,r):
        range,low=[],[0]*2
        vl,vr=self.__e,self.__e
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                if(low[0]==0):
                    self.__ancestors_propagate(l)
                    low[0]=1
                self.__propagate(l)
                vl=self.__dot(vl,self.__node[l])
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                if(low[1]==0):
                    self.__ancestors_propagate(r)
                    low[1]=1
                self.__propagate(r)
                vr=self.__dot(self.__node[r],vr)
            r//=2
        return self.__dot(vl,vr)

class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: adjacency list (with weight)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E 
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__tour=[(0,0)]*(2*n)
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__k+=1
        for u in self.__E[v]:
            if u[0]==p: continue
            self.__tour[self.__k]=(u[1],1)
            self.__dfs(u[0],v)
            self.__tour[self.__k]=(-u[1],-1)
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

    @property
    def tour(self):
        return self.__tour

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    # input
    n=int(input())
    E=[[] for _ in range(n)] # adjecency list
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        E[u].append((v,w))
    # build
    tour=EulerTour(E)
    dot=lambda a,b:(a[0]+b[0],a[1]+b[1])
    e=(0,0)
    comp=lambda f,g:g+f
    id=0
    act=lambda f,a:(a[0]+f*a[1],a[1])
    tree=SegmentTree(tour.tour,dot,e,comp,id,act)
    # query
    q=int(input())
    for _ in range(q):
        Q=list(map(int,input().split()))
        if(Q[0]==1):
            tree.add(tour.begin[Q[1]]+1,tour.end[Q[1]],Q[2])
        else:
            print(tree.sum(0,tour.begin[Q[1]]+1)[0])
resolve()
0