結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2024-01-07 13:45:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,645 ms / 2,000 ms |
コード長 | 8,546 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 157,700 KB |
最終ジャッジ日時 | 2024-09-27 19:23:19 |
合計ジャッジ時間 | 33,848 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,mathinput = sys.stdin.readline#区間加算区間最小値ope = lambda x,y : (x[0]+y[0],x[1]+y[1])ide_ele = (0,0)mapping = lambda f,x : (x[0]+f*x[1],x[1])composition = lambda f,g : f+g #g→fの順に作用id_ = 0class 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.logself.data = [e for _ in range(2 * self.size)]self.lz = [id_ for _ in range(self.size)]self.e = eself.op = opeself.mapping = mappingself.composition = compositionself.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.identitydef set(self, p, x):p += self.sizefor i in range(self.log, 0, -1):self.push(p >> i)self.data[p] = xfor i in range(1, self.log + 1):self.update(p >> i)def get(self, p):p += self.sizefor 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.el += self.sizer += self.sizefor 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.ewhile l < r:if l & 1:sml = self.op(sml, self.data[l])l += 1if r & 1:r -= 1smr = self.op(self.data[r], smr)l >>= 1r >>= 1return self.op(sml, smr)def all_prod(self):return self.data[1]def apply_point(self, p, f):p += self.sizefor 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: returnl += self.sizer += self.sizefor 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, rwhile l < r:if l & 1:self.all_apply(l, f)l += 1if r & 1:r -= 1self.all_apply(r, f)l >>= 1r >>= 1l, r = l2, r2for 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.nl += self.sizefor i in range(self.log, 0, -1):self.push(l >> i)sm = self.ewhile 1:while i % 2 == 0:l >>= 1if not g(self.op(sm, self.data[l])):while l < self.size:self.push(l)l *= 2if g(self.op(sm, self.data[l])):sm = self.op(sm, self.data[l])l += 1return l - self.sizesm = self.op(sm, self.data[l])l += 1if l & -l == l:breakreturn self.ndef min_left(self, r, g):if r == 0:return 0r += self.sizefor i in range(self.log, 0, -1):self.push((r - 1) >> i)sm = self.ewhile 1:r -= 1while r > 1 and r % 2 == 1:r >>= 1if not g(self.op(self.data[r], sm)):while r < self.size:self.push(r)r = 2 * r + 1if g(self.op(self.data[r], sm)):sm = self.op(self.data[r], sm)r -= 1return r + 1 - self.sizesm = self.op(self.data[r], sm)if r & -r == r:breakreturn 0class HLD():### HL分解をしてIDを振りなおしたものに対して、パスに含まれる区間を返す### SegTreeにのせる配列はIDを並び替えたものdef __init__(self,e,root=0):self.N = len(e)self.e = epar = [-1]*Nsub = [-1]*Nself.root = rootdist = [-1]*Nv = deque()dist[root]=0v.append(root)while v:x = v.popleft()for ix in e[x]:if dist[ix] !=-1:continuedist[ix] = dist[x] + 1v.append(ix)H = [(-dist[i],i) for i in range(N)]H.sort()for h,i in H:tmp = 1for ix in e[i]:if sub[ix] == -1:par[i]= ixelse:tmp += sub[ix]sub[i] = tmpself.ID = [-1]*Nself.ID[self.root]=0self.HEAD = [-1]*Nhead = [-1]*Nself.PAR = [-1]*Nvisited = [False]*Nself.HEAD[0]=0head[self.root]=0depth = [-1]*Ndepth[self.root]=0self.DEPTH = [-1]*Nself.DEPTH[0]=0cnt = 0v = deque([self.root])self.SUB = [0]*Nself.SUB[0] = Nwhile v:x = v.popleft()visited[x]=Trueself.ID[x]=cntcnt += 1n = len(self.e[x])tmp = [(sub[ix],ix) for ix in self.e[x]]tmp.sort()flg = 0if x==self.root:flg -= 1for _,ix in tmp:flg += 1if visited[ix]:continuev.appendleft(ix)if flg==n-1:head[ix] = head[x]depth[ix] = depth[x]else:head[ix] = ixdepth[ix] = depth[x]+1for i in range(self.N):self.PAR[self.ID[i]] = self.ID[par[i]]self.HEAD[self.ID[i]] = self.ID[head[i]]self.DEPTH[self.ID[i]] = depth[i]self.SUB[self.ID[i]] = sub[i]def path_query(self,l,r):L = self.ID[l]R = self.ID[r]res = []if self.DEPTH[L]<self.DEPTH[R]:L,R = R,Lwhile self.DEPTH[L] != self.DEPTH[R]:tmp = (self.HEAD[L],L+1)res.append(tmp)L = self.PAR[self.HEAD[L]]while self.HEAD[L] != self.HEAD[R]:tmp = (self.HEAD[L],L+1)res.append(tmp)L = self.PAR[self.HEAD[L]]tmp = (self.HEAD[R],R+1)res.append(tmp)R = self.PAR[self.HEAD[R]]if L>R:L,R = R,Ltmp = (L,R+1)res.append(tmp)return resdef sub_query(self,k):K = self.ID[k]return (K,K+self.SUB[K])N = int(input())e = [[] for _ in range(N)]W = [0]*Nfor _ in range(N-1):u,v,w = map(int,input().split())e[u].append(v)e[v].append(u)W[v] = wQ = int(input())hld = HLD(e)B = [(0,1)]*NID = hld.ID[:]for i,idx in enumerate(ID):B[idx] = (W[i],1)T = lazy_segtree(B,ope,ide_ele,mapping,composition,id_)for _ in range(Q):query = tuple(map(int,input().split()))if query[0]==1:a,x = query[1:]l,r = hld.sub_query(a)T.apply(l+1,r,x)else:b = query[1]tmp = 0for l,r in hld.path_query(0,b):tmp += T.prod(l,r)[0]print(tmp)