#include #ifdef DEBUG #include #else #define dump(...) ((void)0) #endif template bool chmin(T &a, const U &b){ return (a > b ? a = b, true : false); } template bool chmax(T &a, const U &b){ return (a < b ? a = b, true : false); } template void fill_array(T (&a)[N], const U &v){ std::fill((U*)a, (U*)(a + N), v); } template auto make_vector(const std::array &a, T value = T()){ static_assert(I >= 1); static_assert(N >= 1); if constexpr (I == 1){ return std::vector(a[N - I], value); }else{ return std::vector(a[N - I], make_vector(a, value)); } } template std::ostream& operator<<(std::ostream &s, const std::vector &a){ for(auto it = a.begin(); it != a.end(); ++it){ if(it != a.begin()) s << " "; s << *it; } return s; } template std::istream& operator>>(std::istream &s, std::vector &a){ for(auto &x : a) s >> x; return s; } /** * @title Basic graph * @docs graph.md */ template 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 struct Graph { using weight_type = T; using edge_type = Edge; std::vector>> 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 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 using Tree = Graph; /** * @title Rooting * @docs rooting.md */ template void rooting(Tree &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 struct FixPoint : F { explicit constexpr FixPoint(F &&f) noexcept : F(std::forward(f)){} template constexpr auto operator()(Args &&... args) const { return F::operator()(*this, std::forward(args)...); } }; template inline constexpr auto make_fix_point(F &&f){ return FixPoint(std::forward(f)); } template inline constexpr auto make_fix_point(F &f){ return FixPoint(std::forward(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 a(N), b(N); std::cin >> a >> b; Tree tree(N); tree.read<1, false, false>(N - 1); rooting(tree, 0); auto dp = make_vector({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; }