結果

問題 No.1221 木 *= 3
ユーザー 👑 NachiaNachia
提出日時 2020-09-28 21:34:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 877 bytes
コンパイル時間 1,639 ms
コンパイル使用メモリ 167,972 KB
実行使用メモリ 23,328 KB
最終ジャッジ日時 2023-09-15 13:09:17
合計ジャッジ時間 6,456 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,540 KB
testcase_01 AC 3 ms
9,532 KB
testcase_02 AC 3 ms
9,552 KB
testcase_03 AC 3 ms
9,600 KB
testcase_04 AC 3 ms
9,552 KB
testcase_05 AC 3 ms
9,592 KB
testcase_06 AC 3 ms
9,536 KB
testcase_07 AC 181 ms
23,328 KB
testcase_08 AC 177 ms
23,068 KB
testcase_09 AC 179 ms
23,160 KB
testcase_10 AC 179 ms
22,992 KB
testcase_11 AC 179 ms
23,048 KB
testcase_12 AC 162 ms
16,652 KB
testcase_13 AC 155 ms
16,768 KB
testcase_14 AC 157 ms
16,728 KB
testcase_15 AC 159 ms
16,716 KB
testcase_16 AC 158 ms
16,860 KB
testcase_17 AC 185 ms
16,832 KB
testcase_18 AC 179 ms
16,816 KB
testcase_19 AC 178 ms
16,736 KB
testcase_20 AC 185 ms
16,768 KB
testcase_21 AC 179 ms
16,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

struct Edge { int u, v; LL score; };

int N;
LL A[200000][2];
Edge J[200000];
vector<int> E[100000];

LL Score[100000][2];
int P[100000];

void dfs(int p) {
	Score[p][0] = A[p][0];
	Score[p][1] = 0;
	for (int j : E[p]) {
		int to = J[j].v;
		if (P[p] == to) continue;
		P[to] = p;
		dfs(to);
		Score[p][0] += max(Score[to][0], Score[to][1]);
		Score[p][1] += max(Score[to][0], Score[to][1] + J[j].score);
	}
}

int main() {
	cin >> N;
	rep(j, 2) rep(i, N) cin >> A[i][j];
	rep(i, N - 1) {
		int u, v; cin >> u >> v; u--; v--;
		J[i] = { u,v,A[u][1] + A[v][1] };
		J[i + N] = { v,u,A[u][1] + A[v][1] };
		E[u].push_back(i);
		E[v].push_back(i + N);
	}

	P[0] = -1;
	dfs(0);

	cout << max(Score[0][0], Score[0][1]) << endl;

	return 0;
}
0