提交时间:2023-12-02 19:30:13

运行 ID: 23880

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 9; vector<int> G[N]; int n, q, K, a[2][N]; bool chk1() { for (int i = 1; i <= n; i++) { if (a[1][i] > 1) return 0; } return 1; } LL dp[N][3][2]; void dfs(int u, int fa) { dp[u][0][0] = a[0][u], dp[u][1][0] = a[1][u], dp[u][2][0] = 0, dp[u][1][1] = a[1][u]; int cnt = 0; for (int v : G[u]) { if (v == fa) continue; dfs(v, u); cnt++; dp[u][0][0] += max({dp[v][0][0], dp[v][1][0], dp[v][2][0]}); dp[u][2][0] += max({dp[v][0][0], dp[v][1][0], dp[v][2][0], dp[v][1][1]}); dp[u][1][1] += max({dp[v][0][0], dp[v][1][0]}); } if (!cnt) { dp[u][1][0] = -4e18, dp[u][1][1] = a[1][u]; return; } LL fl = 0, sum = 0, mn = 4e18; for (int v : G[u]) { if (v == fa) continue; sum += max({dp[v][0][0], dp[v][1][0], dp[v][2][0]}); if (dp[v][2][0] >= dp[v][0][0] && dp[v][2][0] >= dp[v][1][0]) { fl = 1; } else { mn = min(mn, max(dp[v][0][0], dp[v][1][0]) - dp[v][2][0]); } } if (fl) dp[u][1][0] += sum; else dp[u][1][0] += (sum - mn); } LL ans[N], sum[N]; void dfs(int u, int fa, int d) { sum[d] += max(a[0][u], a[1][u]); ans[d] += max({dp[u][0][0], dp[u][1][0], dp[u][2][0], dp[u][1][1]}); for (int v : G[u]) if (v != fa) dfs(v, u, d + 1); } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[0][i]); } for (int i = 1; i <= n; i++) { scanf("%d", &a[1][i]); } scanf("%d", &K); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } LL sum1 = 0, sum2 = 0; for (int i = 1; i <= n; i++) { sum1 += a[0][i], sum2 += max(a[0][i], a[1][i]); } dfs(K, 0); dfs(K, 0, 0); for (int i = 1; i <= n; i++) { sum[i] += sum[i - 1], ans[i] += sum[i - 1]; } while (q--) { int l; scanf("%d", &l); if (chk1()) { printf("%lld\n", sum1); continue; } else if (l == n) { printf("%lld\n", sum2); continue; } printf("%lld\n", ans[l]); } return 0; }