結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-05 18:55:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 1,359 ms |
コンパイル使用メモリ | 125,176 KB |
最終ジャッジ日時 | 2025-01-14 07:15:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <algorithm>#include <cassert>#include <cctype>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstring>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <vector>#include <list>#define rep(i, n) for (int i = 0; i < (int)(n); ++i)//#define cerr if(false) cerr#ifdef DEBUG#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);#else#define show(...) 42#endifusing namespace std;using ll = long long;using pii = pair<int, int>;template <typename T, typename S>ostream& operator<<(ostream& os, pair<T, S> a) {os << '(' << a.first << ',' << a.second << ')';return os;}template <typename T>ostream& operator<<(ostream& os, vector<T> v) {for (auto x : v) os << x << ' ';return os;}void debug() {cerr << '\n';}template <typename H, typename... T>void debug(H a, T... b) {cerr << a;if (sizeof...(b)) cerr << ", ";debug(b...);}ll dp[2][100005];vector<int>g[100005];ll a[100005];ll b[100005];void dfs(int s, int p){for(int x: g[s]){if(x == p)continue;dfs(x, s);dp[0][s] += max(dp[0][x], dp[1][x]);dp[1][s] += max(dp[0][x], dp[1][x] + b[s] + b[x]);}dp[0][s] += a[s];}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin >> n;rep(i,n)cin >> a[i];rep(i,n)cin >> b[i];rep(i,n-1){int u,v;cin >> u >> v;u--;v--;g[u].push_back(v);g[v].push_back(u);}dfs(0, -1);cout << max(dp[0][0], dp[1][0]) << endl;}