結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 21:47:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 219 ms / 2,000 ms |
コード長 | 1,127 bytes |
コンパイル時間 | 2,083 ms |
コンパイル使用メモリ | 204,416 KB |
最終ジャッジ日時 | 2025-01-14 05:29:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;void dfs(vector<long long> &dp0, vector<long long> &dp1, vector<vector<int>> &c, vector<int> &a, vector<int> &b, int v = 0){for (int w : c[v]){dfs(dp0, dp1, c, a, b, w);}dp0[v] = a[v];for (int w : c[v]){dp0[v] += max(dp0[w], dp1[w]);}dp1[v] = 0;for (int w : c[v]){dp1[v] += max(dp0[w], dp1[w] + b[v] + b[w]);}}int main(){int N;cin >> N;vector<int> a(N);for (int i = 0; i < N; i++){cin >> a[i];}vector<int> b(N);for (int i = 0; i < N; i++){cin >> b[i];}vector<vector<int>> E(N);for (int i = 0; i < N - 1; i++){int u, v;cin >> u >> v;u--;v--;E[u].push_back(v);E[v].push_back(u);}vector<int> p(N, -1);vector<vector<int>> c(N);queue<int> Q;Q.push(0);while (!Q.empty()){int v = Q.front();Q.pop();for (int w : E[v]){if (w != p[v]){p[w] = v;c[v].push_back(w);Q.push(w);}}}vector<long long> dp0(N);vector<long long> dp1(N);dfs(dp0, dp1, c, a, b);cout << max(dp0[0], dp1[0]) << endl;}