#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll A[100010]; ll B[100010]; vector E[100010]; struct Node { ll value_0; ll value_1; Node(ll value_0 = -1, ll value_1 = -1) { this->value_0 = value_0; this->value_1 = value_1; } }; Node t_dp(int v, int parent = -1) { int child_num = E[v].size(); vector> dp(child_num + 1, vector(2, LLONG_MIN)); dp[0][0] = 0LL; dp[0][1] = 0LL; int i = 0; for (int j = 0; j < child_num; ++j) { int u = E[v][j]; if (u == parent) continue; Node node = t_dp(u, v); // fprintf(stderr, "u: %d, v0: %lld, v1: %lld\n", u, node.value_0, node.value_1); dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + node.value_0); dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + node.value_1 - (B[u])); dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + node.value_0); dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + node.value_1 + B[v]); // fprintf(stderr, "dp - v0: %lld, v1: %lld\n", dp[i + 1][0], dp[i + 1][1]); ++i; } if (parent != -1) { if (i == 0) { return Node(A[v], B[v]); } else { // fprintf(stderr, "A: %lld, B: %lld\n", A[v], B[v]); return Node(dp[i][0] + A[v], dp[i][1] + B[v]); } } else { return Node(dp[i][0] + A[v], dp[i][1]); } } int main() { int N; cin >> N; for (int i = 0; i < N; ++i) { cin >> A[i]; } for (int i = 0; i < N; ++i) { cin >> B[i]; } for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; --u; --v; E[u].push_back(v); E[v].push_back(u); } Node node = t_dp(0, -1); cout << max(node.value_0, node.value_1) << endl; return 0; }