結果
問題 | No.1221 木 *= 3 |
ユーザー |
|
提出日時 | 2021-03-19 15:03:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 327 ms / 2,000 ms |
コード長 | 1,245 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 123,940 KB |
最終ジャッジ日時 | 2024-11-18 09:38:31 |
合計ジャッジ時間 | 6,227 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
def main1(n,a,b,uv):if n==1:return max(a[0],0)ki=[[] for _ in range(n)]for u,v in uv:u,v=u-1,v-1ki[u].append(v)ki[v].append(u)# 頂点vを消したときの最大値# 頂点vを消さないときの最大値tree_order=[]parent=[-1]*ntodo=[[0,-1]]while todo:v,p=todo.pop()tree_order.append(v)parent[v]=pfor nv in ki[v]:if nv==p:continuetodo.append([nv,v])tree_order.reverse()ary=[[] for _ in range(n)]# ary[v]:頂点vが子から遷移してきた値[子のidx,子を消すときの最大,子を消さないときの最大]の配列ans=0for v in tree_order:p=parent[v]if len(ary[v])==0:ary[p].append([v,a[v],0])else:num1=a[v] # 頂点vを消すnum2=0 # 頂点vを消さないfor i,ai,bi in ary[v]:num1+=max(ai,bi)num2+=max(ai,bi+b[i]+b[v])if p>=0:ary[p].append([v,num1,num2])else:ans=max(num1,num2)return ansimport sysinput=sys.stdin.readlineif __name__=='__main__':n=int(input())a=list(map(int,input().split()))b=list(map(int,input().split()))uv=[list(map(int,input().split())) for _ in range(n-1)]ret1=main1(n,a,b,uv)print(ret1)