結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:07:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 1,343 bytes |
コンパイル時間 | 1,529 ms |
コンパイル使用メモリ | 168,916 KB |
実行使用メモリ | 18,560 KB |
最終ジャッジ日時 | 2024-11-26 12:57:28 |
合計ジャッジ時間 | 4,012 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define pb push_back#define fi first#define se secondtypedef pair<ll, ll> P;using VP = vector<P>;using VVP = vector<VP>;using VI = vector<ll>;using VVI = vector<VI>;using VVVI = vector<VVI>;const int inf = 1e9 + 7;const ll INF = 1LL << 61;const ll mod = 1e9 + 7;template <class T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}template <class T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}int n;vector<int> E[101010];ll dp[101010][2];ll a[101010], b[101010];void dfs(int cu, int pa = -1) {dp[cu][0] = a[cu];dp[cu][1] = 0;for (ll to : E[cu])if (to != pa) {dfs(to, cu);dp[cu][0] += max(dp[to][0], dp[to][1]);dp[cu][1] += max(dp[to][0], dp[to][1] + b[cu] + b[to]);}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int i, j;cin >> n;for (i = 0; i < n; i++) cin >> a[i];for (i = 0; i < n; i++) cin >> b[i];for (i = 0; i < n - 1; i++) {ll u, v;cin >> u >> v;u--;v--;E[u].pb(v);E[v].pb(u);}dfs(0, -1);cout << max(dp[0][0], dp[0][1]) << endl;}