#line 1 "yu.cpp" #include #line 5 "Library\\config.hpp" namespace config { const auto start_time{std::chrono::system_clock::now()}; int64_t elapsed() { using namespace std::chrono; const auto end_time{system_clock::now()}; return duration_cast(end_time - start_time).count(); } __attribute__((constructor)) void setup() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); #ifdef _buffer_check atexit([]{ ofstream cnsl("CON"); char bufc; if(cin >> bufc) cnsl << "\n\033[43m\033[30mwarning: buffer not empty.\033[0m\n\n"; }); #endif } unsigned cases(void), caseid = 1; template void main() { for(const unsigned total = cases(); caseid <= total; ++caseid) C(); } } // namespace config #line 3 "Library\\gcc_builtin.hpp" namespace workspace { constexpr int clz32(const uint32_t &n) noexcept { return __builtin_clz(n); } constexpr int clz64(const uint64_t &n) noexcept{ return __builtin_clzll(n); } constexpr int ctz(const uint64_t &n) noexcept { return __builtin_ctzll(n); } constexpr int popcnt(const uint64_t &n) noexcept { return __builtin_popcountll(n); } } // namespace workspace #line 2 "Library\\gcc_option.hpp" #ifdef ONLINE_JUDGE #pragma GCC optimize("O3") #pragma GCC target("avx,avx2") #pragma GCC optimize("unroll-loops") #endif #line 5 "Library\\utils\\binary_search.hpp" namespace workspace { // binary search on discrete range. template , bool>, std::nullptr_t> = nullptr> iter_type binary_search(iter_type ok, iter_type ng, pred_type pred) { assert(ok != ng); intmax_t dist(ng - ok); while(std::abs(dist) > 1) { iter_type mid(ok + dist / 2); if(pred(mid)) ok = mid, dist -= dist / 2; else ng = mid, dist /= 2; } return ok; } // binary search on real numbers. template , bool>, std::nullptr_t> = nullptr> real_type binary_search(real_type ok, real_type ng, const real_type eps, pred_type pred) { assert(ok != ng); while(std::abs(ok - ng) > eps) { real_type mid{(ok + ng) / 2}; (pred(mid) ? ok : ng) = mid; } return ok; } } // namespace workspace #line 3 "Library\\utils\\casefmt.hpp" namespace workspace { std::ostream &casefmt(std::ostream& os) { return os << "Case #" << config::caseid << ": "; } } // namespace workspace #line 3 "Library\\utils\\chval.hpp" namespace workspace { template > bool chle(T &x, const T &y, Comp comp = Comp()) { return comp(y, x) ? x = y, true : false; } template > bool chge(T &x, const T &y, Comp comp = Comp()) { return comp(x, y) ? x = y, true : false; } } // namespace workspace #line 3 "Library\\utils\\fixed_point.hpp" namespace workspace { // specify the return type of lambda. template class fixed_point { lambda_type func; public: fixed_point(lambda_type &&f) : func(std::move(f)) {} template auto operator()(Args &&... args) const { return func(*this, std::forward(args)...); } }; } // namespace workspace #line 2 "Library\\utils\\sfinae.hpp" #include template class trait> using enable_if_trait_type = typename std::enable_if::value>::type; template using element_type = std::remove_const_t()))>>; #line 7 "Library\\utils\\hash.hpp" namespace workspace { template struct hash : std::hash {}; template struct hash> { size_t operator()(uint64_t x) const { static const uint64_t m = std::random_device{}(); x ^= x >> 23; // x *= 0x2127599bf4325c37ULL; x ^= m; x ^= x >> 47; return x - (x >> 32); } }; template size_t hash_combine(const size_t &seed, const Key &key) { return seed ^ (hash()(key) + 0x9e3779b9 /* + (seed << 6) + (seed >> 2) */ ); } template struct hash> { size_t operator()(const std::pair &pair) const { return hash_combine(hash()(pair.first), pair.second); } }; template class hash> { template ::value - 1> struct tuple_hash { static uint64_t apply(const Tuple &t) { return hash_combine(tuple_hash::apply(t), std::get(t)); } }; template struct tuple_hash { static uint64_t apply(const Tuple &t) { return 0; } }; public: uint64_t operator()(const std::tuple &t) const { return tuple_hash>::apply(t); } }; template struct hash_table_wrapper : hash_table { using key_type = typename hash_table::key_type; size_t count(const key_type &key) const { return hash_table::find(key) != hash_table::end(); } template auto emplace(Args&&... args) { return hash_table::insert(typename hash_table::value_type(args...)); } }; template using cc_hash_table = hash_table_wrapper<__gnu_pbds::cc_hash_table>>; template using gp_hash_table = hash_table_wrapper<__gnu_pbds::gp_hash_table>>; template using unordered_map = std::unordered_map>; template using unordered_set = std::unordered_set>; } // namespace workspace #line 3 "Library\\utils\\iostream_overload.hpp" namespace std { template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } template struct tuple_is { static istream &apply(istream &is, tuple_t &t) { tuple_is::apply(is, t); return is >> get(t); } }; template struct tuple_is { static istream &apply(istream &is, tuple_t &t) { return is; } }; template istream &operator>>(istream &is, tuple &t) { return tuple_is, tuple_size>::value - 1>::apply(is, t); } template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { tuple_os::apply(os, t); return os << ' ' << get(t); } }; template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { return os << get<0>(t); } }; template struct tuple_os { static ostream &apply(ostream &os, const tuple_t &t) { return os; } }; template ostream &operator<<(ostream &os, const tuple &t) { return tuple_os, tuple_size>::value - 1>::apply(os, t); } template , string>::value, nullptr_t> = nullptr> istream& operator>>(istream& is, Container &cont) { for(auto&& e : cont) is >> e; return is; } template , string>::value, nullptr_t> = nullptr> ostream& operator<<(ostream& os, const Container &cont) { bool flag = 1; for(auto&& e : cont) flag ? flag = 0 : (os << ' ', 0), os << e; return os; } } // namespace std #line 3 "Library\\utils\\read.hpp" namespace workspace { // read with std::cin. template struct read { typename std::remove_const::type value; template read(types... args) : value(args...) { std::cin >> value; } operator T() const { return value; } }; template <> struct read { template operator T() const { T value; std::cin >> value; return value; } }; } // namespace workspace #line 13 "yu.cpp" namespace workspace { constexpr char eol = '\n'; using namespace std; using i64 = int_least64_t; using p32 = pair; using p64 = pair; template > using priority_queue = std::priority_queue, Comp>; template using stack = std::stack>; struct solver; } // namespace workspace int main() { config::main(); } unsigned config::cases() { // return -1; // not specify // int t; std::cin >> t; return t; // given return 1; } struct workspace::solver { int n; vector a, b; vector> tr; vector dp0, dp1; solver() : n(read()), a(n), b(n), tr(n), dp0(n), dp1(n) { // start here! cin >> a >> b; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; --u, --v; tr[u].emplace_back(v); tr[v].emplace_back(u); } const int root = 0; dfs(root, -1); cout << max(dp0[root], dp1[root]) << eol; } void dfs(int now, int pre) { i64 sum = 0, sum2 = 0; priority_queue q; for (auto to : tr[now]) { if (to == pre) { continue; } dfs(to, now); sum += dp0[to]; sum2 += max(dp0[to], dp1[to]); q.push(dp1[to] + b[to] - dp0[to]); } dp0[now] = sum2 + a[now]; auto &ref = dp1[now]; ref = sum; for (int i = 1; i < size(tr[now]); i++) { sum += q.top(); sum += b[now]; q.pop(); chge(ref, sum); } } };