結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.readlinesys.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=0QUE=[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]=xChild[x].append(to)QUE.append(to)Children=[1]*(N+1)for x in TOP_SORT[::-1]: #(自分を含む)子ノードの数を調べるChildren[Parent[x]]+=Children[x]USE=[0]*NGroup=[i for i in range(N)]for x in TOP_SORT: # HL分解によるグループ分けUSE[x]=1MAX_children=0select_node=0for to in E[x]:if USE[to]==0 and Children[to]>MAX_children:select_node=toMAX_children=Children[to]for to in E[x]:if USE[to]==0 and to==select_node:Group[to]=Group[x]def LCA(a,b): # HL分解を利用してLCAを求める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 aelse:return bfrom functools import lru_cache@lru_cache(maxsize=None)def calc(x):if x==N:return 0if x==ROOT:return U[x]else:return U[x]+calc(Parent[x])ANS=0m=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)