結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:51:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 713 ms / 2,000 ms |
コード長 | 1,354 bytes |
コンパイル時間 | 4,255 ms |
コンパイル使用メモリ | 77,800 KB |
実行使用メモリ | 83,320 KB |
最終ジャッジ日時 | 2024-11-26 20:46:27 |
合計ジャッジ時間 | 16,116 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main {static int n;static int[] a, b;static List<List<Integer>> list;static long[] dp0, dp1;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(br.readLine());String[] sa = br.readLine().split(" ");a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(sa[i]);}sa = br.readLine().split(" ");b = new int[n];for (int i = 0; i < n; i++) {b[i] = Integer.parseInt(sa[i]);}list = new ArrayList<>(n);for (int i = 0; i < n; i++) {list.add(new ArrayList<>());}for (int i = 0; i < n - 1; i++) {sa = br.readLine().split(" ");int u = Integer.parseInt(sa[0]) - 1;int v = Integer.parseInt(sa[1]) - 1;list.get(u).add(v);list.get(v).add(u);}br.close();dp0 = new long[n];dp1 = new long[n];dfs(0, -1);System.out.println(Math.max(dp0[0], dp1[0]));}static void dfs(int cur, int p) {for (int next : list.get(cur)) {if (next == p) {continue;}dfs(next, cur);dp0[cur] += Math.max(dp0[next], dp1[next]);dp1[cur] += Math.max(dp0[next], dp1[next] + b[cur] + b[next]);}dp0[cur] += a[cur];}}