結果
問題 | No.1221 木 *= 3 |
ユーザー |
|
提出日時 | 2020-09-04 23:06:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 4,613 bytes |
コンパイル時間 | 2,466 ms |
コンパイル使用メモリ | 206,784 KB |
最終ジャッジ日時 | 2025-01-14 06:22:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#ifdef DEBUG#include <Mylib/Debug/debug.cpp>#else#define dump(...) ((void)0)#endiftemplate <typename T, typename U>bool chmin(T &a, const U &b){return (a > b ? a = b, true : false);}template <typename T, typename U>bool chmax(T &a, const U &b){return (a < b ? a = b, true : false);}template <typename T, size_t N, typename U>void fill_array(T (&a)[N], const U &v){std::fill((U*)a, (U*)(a + N), v);}template <typename T, size_t N, size_t I = N>auto make_vector(const std::array<int, N> &a, T value = T()){static_assert(I >= 1);static_assert(N >= 1);if constexpr (I == 1){return std::vector<T>(a[N - I], value);}else{return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));}}template <typename T>std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){for(auto it = a.begin(); it != a.end(); ++it){if(it != a.begin()) s << " ";s << *it;}return s;}template <typename T>std::istream& operator>>(std::istream &s, std::vector<T> &a){for(auto &x : a) s >> x;return s;}/*** @title Basic graph* @docs graph.md*/template <typename T>struct Edge {int from, to;T cost;int index = -1;Edge(){}Edge(int from, int to, T cost): from(from), to(to), cost(cost){}Edge(int from, int to, T cost, int index): from(from), to(to), cost(cost), index(index){}};template <typename T>struct Graph {using weight_type = T;using edge_type = Edge<T>;std::vector<std::vector<Edge<T>>> data;auto& operator[](size_t i){return data[i];}const auto& operator[](size_t i) const {return data[i];}auto begin() const {return data.begin();}auto end() const {return data.end();}Graph(){}Graph(int N): data(N){}bool empty() const {return data.empty();}int size() const {return data.size();}void add_edge(int i, int j, T w, int index = -1){data[i].emplace_back(i, j, w, index);}void add_undirected(int i, int j, T w, int index = -1){add_edge(i, j, w, index);add_edge(j, i, w, index);}template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>void read(int M){for(int i = 0; i < M; ++i){int u, v; std::cin >> u >> v;u -= I;v -= I;T w = 1;if(WEIGHTED) std::cin >> w;if(DIRECTED) add_edge(u, v, w, i);else add_undirected(u, v, w, i);}}};template <typename T>using Tree = Graph<T>;/*** @title Rooting* @docs rooting.md*/template <typename T>void rooting(Tree<T> &tree, int cur, int par = -1){if(par != -1){for(auto it = tree[cur].begin(); it != tree[cur].end(); ++it){if(it->to == par){tree[cur].erase(it);break;}}}for(auto &e : tree[cur]){rooting(tree, e.to, cur);}}/*** @title Fixed point combinator* @docs fix_point.md*/template <typename F>struct FixPoint : F {explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)){}template <typename... Args>constexpr auto operator()(Args &&... args) const {return F::operator()(*this, std::forward<Args>(args)...);}};template <typename F>inline constexpr auto make_fix_point(F &&f){return FixPoint<F>(std::forward<F>(f));}template <typename F>inline constexpr auto make_fix_point(F &f){return FixPoint<F>(std::forward<F>(f));}namespace solver{void init(){std::cin.tie(0);std::ios::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(12);std::cerr << std::fixed << std::setprecision(12);std::cin.exceptions(std::ios_base::failbit);}constexpr int64_t INF = 1LL << 50;void solve(){int N; std::cin >> N;std::vector<int64_t> a(N), b(N); std::cin >> a >> b;Tree<int> tree(N);tree.read<1, false, false>(N - 1);rooting(tree, 0);auto dp = make_vector<int64_t, 2>({N, 2}, -INF);auto rec =make_fix_point([&](auto &&rec, int cur) -> void {for(auto &e : tree[cur]){rec(e.to);}dp[cur][0] = a[cur];for(auto &e : tree[cur]){dp[cur][0] += std::max(dp[e.to][0], dp[e.to][1]);}dp[cur][1] = 0;for(auto &e : tree[cur]){dp[cur][1] += std::max(dp[e.to][0], dp[e.to][1] + b[cur] + b[e.to]);}});rec(0);int64_t ans = std::max(dp[0][0], dp[0][1]);std::cout << ans << "\n";}}int main(){solver::init();while(true){try{solver::solve();}catch(const std::istream::failure &e){break;}}return 0;}