結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2022-01-12 01:54:37 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 1,841 bytes |
コンパイル時間 | 1,549 ms |
コンパイル使用メモリ | 141,160 KB |
実行使用メモリ | 36,480 KB |
最終ジャッジ日時 | 2024-11-14 12:46:04 |
合計ジャッジ時間 | 6,850 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;ll A[100010];ll B[100010];vector<int> E[100010];struct Node {ll value_0;ll value_1;Node(ll value_0 = -1, ll value_1 = -1) {this->value_0 = value_0;this->value_1 = value_1;}};Node t_dp(int v, int parent = -1) {int child_num = E[v].size();vector<vector<ll>> dp(child_num + 1, vector<ll>(2, LLONG_MIN));dp[0][0] = 0LL;dp[0][1] = 0LL;int i = 0;for (int j = 0; j < child_num; ++j) {int u = E[v][j];if (u == parent) continue;Node node = t_dp(u, v);// fprintf(stderr, "u: %d, v0: %lld, v1: %lld\n", u, node.value_0, node.value_1);dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + node.value_0);dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + node.value_1 - (B[u]));dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + node.value_0);dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + node.value_1 + B[v]);// fprintf(stderr, "dp - v0: %lld, v1: %lld\n", dp[i + 1][0], dp[i + 1][1]);++i;}if (parent != -1) {if (i == 0) {return Node(A[v], B[v]);} else {// fprintf(stderr, "A: %lld, B: %lld\n", A[v], B[v]);return Node(dp[i][0] + A[v], dp[i][1] + B[v]);}} else {return Node(dp[i][0] + A[v], dp[i][1]);}}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;E[u].push_back(v);E[v].push_back(u);}Node node = t_dp(0, -1);cout << max(node.value_0, node.value_1) << endl;return 0;}