結果

問題 No.1221 木 *= 3
コンテスト
ユーザー Nachia
提出日時 2020-09-28 21:34:30
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 877 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,543 ms
コンパイル使用メモリ 169,628 KB
実行使用メモリ 22,732 KB
最終ジャッジ日時 2024-07-02 16:20:36
合計ジャッジ時間 5,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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