結果

問題 No.1221 木 *= 3
ユーザー 👑 NachiaNachia
提出日時 2020-09-28 21:34:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 877 bytes
コンパイル時間 1,543 ms
コンパイル使用メモリ 169,628 KB
実行使用メモリ 22,732 KB
最終ジャッジ日時 2024-07-02 16:20:36
合計ジャッジ時間 5,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,804 KB
testcase_01 AC 4 ms
9,804 KB
testcase_02 AC 3 ms
9,676 KB
testcase_03 AC 3 ms
9,676 KB
testcase_04 AC 3 ms
9,676 KB
testcase_05 AC 3 ms
9,672 KB
testcase_06 AC 3 ms
9,676 KB
testcase_07 AC 163 ms
22,192 KB
testcase_08 AC 154 ms
22,028 KB
testcase_09 AC 156 ms
22,068 KB
testcase_10 AC 169 ms
22,348 KB
testcase_11 AC 165 ms
22,732 KB
testcase_12 AC 153 ms
16,892 KB
testcase_13 AC 139 ms
15,880 KB
testcase_14 AC 152 ms
15,752 KB
testcase_15 AC 153 ms
16,084 KB
testcase_16 AC 145 ms
16,340 KB
testcase_17 AC 165 ms
15,652 KB
testcase_18 AC 160 ms
16,972 KB
testcase_19 AC 165 ms
15,816 KB
testcase_20 AC 163 ms
16,716 KB
testcase_21 AC 169 ms
16,208 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