結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:29:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 1,791 ms |
コンパイル使用メモリ | 95,968 KB |
最終ジャッジ日時 | 2025-01-14 05:59:36 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;struct Graph {struct Vertex { int n, a, b; };struct Edge { int i, n; };Graph(int n, int m) : v(n, { -1, 0, 0 }), e(m), n(n), m(0) {}void add_edge(int i, int j) {e[m] = { j, v[i].n };v[i].n = m;m++;}void dfs(int i, int p, ll &s0, ll &s1) {ll r0 = v[i].a, r1 = 0;for (int j = v[i].n; j >= 0; j = e[j].n) {Edge& o = e[j];if (o.i == p) continue;ll t0, t1;dfs(o.i, i, t0, t1);r0 += max(t0, t1);r1 += max(t0, t1 + v[o.i].b + v[i].b);}s0 = r0; s1 = r1;}void solve() {for (int i = 0; i < n; i++) {cin >> v[i].a;}for (int i = 0; i < n; i++) {cin >> v[i].b;}for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;a--; b--;add_edge(a, b);add_edge(b, a);}ll s0, s1;dfs(0, -1, s0, s1);cout << max(s0, s1) << endl;}vector<Vertex> v;vector<Edge> e;int n, m;};int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;Graph g(n, (n - 1) * 2);g.solve();return 0;}