結果

問題 No.900 aδδitivee
コンテスト
ユーザー sasa8uyauya
提出日時 2026-03-11 22:46:43
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 631 ms / 2,000 ms
コード長 1,376 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 415 ms
コンパイル使用メモリ 85,324 KB
実行使用メモリ 101,360 KB
最終ジャッジ日時 2026-03-11 22:47:00
合計ジャッジ時間 16,281 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n=int(input())
e=[[] for i in range(n)]
a=[0]*n
for i in range(n-1):
  u,v,w=map(int,input().split())
  e[u]+=[v]
  a[v]=w

o=[]
y=[0]*n
g=[0]*n
d=[0]*n
v=[0]*n
q=[0]
while len(q)>0:
  s=q[-1]
  if v[s]==0:
    v[s]=1
    o+=[s]
    y[s]=len(o)-1
    for t in e[s]:
      q+=[t]
      d[t]=d[s]+1
      a[t]+=a[s]
  else:
    g[s]=1+sum(g[t] for t in e[s])
    q.pop()

B=317

std=[n]*B*B
for i in range(n):
  std[i]=d[o[i]]
stm=[min(std[y*B:y*B+B]) for y in range(B)]

st1=[0]*B*B
st2=[(0,0)]*B

def ADD(l,r,u,v):
  yl=l//B
  yr=r//B
  for y in [yl,yr]:
    p1,p2=st2[y]
    for i in range(y*B,y*B+B):
      if y<n:
        st1[i]+=p1*(std[i]-stm[y])+p2
    st2[y]=(0,0)
  if yl==yr:
    for i in range(l,r+1):
      if y<n:
        st1[i]+=v*(std[i]-u)
  else:
    for i in range(l,yl*B+B):
      if y<n:
        st1[i]+=v*(std[i]-u)
    for i in range(yr*B,r+1):
      if y<n:
        st1[i]+=v*(std[i]-u)
    for i in range(yl+1,yr):
      p1,p2=st2[i]
      st2[i]=(p1+v,p2+v*(stm[i]-u))
  return

def GET(x):
  y=x//B
  p1,p2=st2[y]
  for i in range(y*B,y*B+B):
    if y<n:
      st1[i]+=p1*(std[i]-stm[y])+p2
  st2[y]=(0,0)
  return st1[x]

for i in range(n):
  st1[i]=a[o[i]]

Q=int(input())
for _ in range(Q):
  q=list(map(int,input().split()))
  t=q[0]
  if t==1:
    t,a,x=q
    if g[a]>0:
      ADD(y[a]+1,y[a]+g[a]-1,d[a],x)
  else:
    t,b=q
    print(GET(y[b]))
0