結果

問題 No.1221 木 *= 3
コンテスト
ユーザー anagohirame
提出日時 2020-08-22 01:23:46
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 294 ms / 2,000 ms
コード長 667 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,415 ms
コンパイル使用メモリ 197,680 KB
最終ジャッジ日時 2025-01-13 06:41:52
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int MAX = 100010;

vector<ll> dp0(MAX, 0), dp1(MAX, 0), a(MAX), b(MAX);
vector<vector<int>> adj(MAX);

void dfs(int i, int p) {
	dp0[i] += a[i];
	for (int j : adj[i]) {
		if (j == p) continue;
		dfs(j, i);
		dp0[i] += max(dp0[j], dp1[j]);
		dp1[i] += max(dp0[j], dp1[j] + b[i] + b[j]);
	}
	return;
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) cin >> b[i];
	for (int i = 0; i < n-1; ++i) {
		int u, v; cin >> u >> v; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0, -1);
	cout << max(dp0[0], dp1[0]) << endl;
	return 0;
}
0