/* -*- coding: utf-8 -*- * * 899.cc: No.899 ç²’atheree - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_E2 = 1 << 18; // = 262144 const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; typedef queue qi; typedef vector vi; template struct SegTreeDly { int n, e2; T nodes[MAX_E2], dls[MAX_E2], undef; SegTreeDly() {} void init(int _n, T _undef) { n = _n; undef = _undef; for (e2 = 1; e2 < n; e2 <<= 1); fill(dls, dls + MAX_E2, undef); } T &get(int i) { return nodes[e2 - 1 + i]; } void set(int i, T v) { get(i) = v; } void setall() { for (int j = e2 - 2; j >= 0; j--) nodes[j] = nodes[j * 2 + 1] + nodes[j * 2 + 2]; } void _update(int k, int l) { if (dls[k] != undef) { int k0 = k * 2 + 1, k1 = k0 + 1, hl = (l >> 1); nodes[k0] = dls[k] * hl; dls[k0] = dls[k]; nodes[k1] = dls[k] * hl; dls[k1] = dls[k]; dls[k] = undef; } } void set_range(int r0, int r1, T v, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return; if (r0 <= i0 && i1 <= r1) { nodes[k] = v * (i1 - i0); dls[k] = v; return; } _update(k, i1 - i0); int im = (i0 + i1) / 2; int k0 = k * 2 + 1, k1 = k0 + 1; set_range(r0, r1, v, k0, i0, im); set_range(r0, r1, v, k1, im, i1); nodes[k] = nodes[k0] + nodes[k1]; } void set_range(int r0, int r1, T v) { set_range(r0, r1, v, 0, 0, e2); } T sum_range(int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return 0; if (r0 <= i0 && i1 <= r1) return nodes[k]; _update(k, i1 - i0); int im = (i0 + i1) / 2; T v0 = sum_range(r0, r1, k * 2 + 1, i0, im); T v1 = sum_range(r0, r1, k * 2 + 2, im, i1); return v0 + v1; } T sum_range(int r0, int r1) { return sum_range(r0, r1, 0, 0, e2); } }; /* global variables */ vi nbrs[MAX_N]; int prts[MAX_N], rls[MAX_N][3], rrs[MAX_N][3], cns[MAX_N]; SegTreeDly st; int xls[10], xrs[10]; /* subroutines */ inline void setmin(int &a, int b) { if (a > b) a = b; } inline void setmax(int &a, int b) { if (a < b) a = b; } inline void addrange(int &pl, int &pr, int l, int r) { if (l >= 0) { if (pl < 0) pl = l, pr = r; else { setmin(pl, l); setmax(pr, r); } } } /* main */ int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); nbrs[u].push_back(v); nbrs[v].push_back(u); } memset(rls, -1, sizeof(rls)); memset(rrs, -1, sizeof(rrs)); prts[0] = -1; qi q; q.push(0); for (int k = 0; ! q.empty(); k++) { int u = q.front(); q.pop(); rls[u][0] = k, rrs[u][0] = k + 1; int &up = prts[u]; vi &nbru = nbrs[u]; for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &v = *vit; if (v != up) { prts[v] = u; cns[u]++; q.push(v); } } } for (int u = 0; u < n; u++) if (cns[u] == 0) q.push(u); while (! q.empty()) { int u = q.front(); q.pop(); int &up = prts[u]; if (up >= 0) { for (int i = 0; i < 2; i++) addrange(rls[up][i + 1], rrs[up][i + 1], rls[u][i], rrs[u][i]); if (--cns[up] == 0) q.push(up); } } for (int u = 0; false && u < n; u++) { printf("%d:", u); for (int i = 0; i < 3; i++) printf("(%d,%d)", rls[u][i], rrs[u][i]); putchar('\n'); } st.init(n, LINF); for (int i = 0; i < n; i++) { int ai; scanf("%d", &ai); st.set(rls[i][0], ai); } st.setall(); int qn; scanf("%d", &qn); while (qn--) { int x; scanf("%d", &x); int xn = 0; if (rls[x][1] >= 0) xls[xn] = rls[x][1], xrs[xn] = rrs[x][1], xn++; if (rls[x][2] >= 0) xls[xn] = rls[x][2], xrs[xn] = rrs[x][2], xn++; int &xp = prts[x]; if (xp < 0) xls[xn] = rls[x][0], xrs[xn] = rrs[x][0], xn++; else { xls[xn] = rls[xp][0], xrs[xn] = rrs[xp][0], xn++; xls[xn] = rls[xp][1], xrs[xn] = rrs[xp][1], xn++; int &xpp = prts[xp]; if (xpp >= 0) xls[xn] = rls[xpp][0], xrs[xn] = rrs[xpp][0], xn++; } ll sum = 0; for (int i = 0; i < xn; i++) sum += st.sum_range(xls[i], xrs[i]); for (int i = 0; i < xn; i++) st.set_range(xls[i], xrs[i], 0); st.set_range(rls[x][0], rrs[x][0], sum); printf("%lld\n", sum); } return 0; }