結果

問題 No.386 貪欲な領主
ユーザー titiatitia
提出日時 2023-01-30 03:07:28
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,947 bytes
コンパイル時間 132 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 55,672 KB
最終ジャッジ日時 2024-06-29 20:51:37
合計ジャッジ時間 7,859 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 14 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N=int(input())
E=[[] for i in range(N)]
for i in range(N-1):
x,y=map(int,input().split())
E[x].append(y)
E[y].append(x)
U=[int(input()) for i in range(N)]
ROOT=0
QUE=[ROOT]
Parent=[-1]*(N+1)
Parent[ROOT]=N # ROOT.
Child=[[] for i in range(N+1)]
TOP_SORT=[] #
while QUE: #
x=QUE.pop()
TOP_SORT.append(x)
for to in E[x]:
if Parent[to]==-1:
Parent[to]=x
Child[x].append(to)
QUE.append(to)
Children=[1]*(N+1)
for x in TOP_SORT[::-1]: #調
Children[Parent[x]]+=Children[x]
USE=[0]*N
Group=[i for i in range(N)]
for x in TOP_SORT: # HL
USE[x]=1
MAX_children=0
select_node=0
for to in E[x]:
if USE[to]==0 and Children[to]>MAX_children:
select_node=to
MAX_children=Children[to]
for to in E[x]:
if USE[to]==0 and to==select_node:
Group[to]=Group[x]
def LCA(a,b): # HLLCA
while Group[a]!=Group[b]:
if Children[Parent[Group[a]]]<Children[Parent[Group[b]]]:
a=Parent[Group[a]]
else:
b=Parent[Group[b]]
if Children[a]>Children[b]:
return a
else:
return b
from functools import lru_cache
@lru_cache(maxsize=None)
def calc(x):
if x==N:
return 0
if x==ROOT:
return U[x]
else:
return U[x]+calc(Parent[x])
ANS=0
m=int(input())
for i in range(m):
a,b,c=map(int,input().split())
x=LCA(a,b)
if x==a:
ANS+=c*(calc(b)-calc(Parent[a]))
elif x==b:
ANS+=c*(calc(a)-calc(Parent[b]))
else:
ANS+=c*(calc(a)+calc(b)-calc(x)-calc(Parent[x]))
print(ANS)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0