using System; using static System.Console; using System.Linq; using System.Collections.Generic; using System.Security.Cryptography; using Microsoft.VisualBasic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); static int[] LList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => int.Parse(ReadLine())).ToArray(); public static void Main() { Solve(); } static void Solve() { var n = NN; var map = NArr(n - 1); var a = NList; var q = NN; var x = LList(q); var tree = new List[n]; for (var i = 0; i < n; ++i) tree[i] = new List(); foreach (var edge in map) { tree[edge[0]].Add(edge[1]); tree[edge[1]].Add(edge[0]); } var dlist = new List>(); var ref1 = new (int b, int e)[n]; var ref2 = new (int b, int e)[n]; var plist = new int[n]; plist[0] = -1; var pos = new (int d, int p)[n]; CreateDList(0, -1, 0, tree, dlist, ref1, ref2, plist, pos); var slist = new LazySegTree[dlist.Count]; for (var i = 0; i < dlist.Count; ++i) { slist[i] = new LazySegTree(dlist[i].Count + 1, new SegOp()); for (var j = 0; j < dlist[i].Count; ++j) slist[i].Set(j, a[dlist[i][j]]); } // for (var f = 0; f < slist.Length; ++f) // { // WriteLine($"dep = {f}"); // for (var g = 0; g < dlist[f].Count; ++g) Write($"({dlist[f][g]}, {slist[f].Get(g)}) "); // WriteLine(); // } var ans = new long[q]; for (var i = 0; i < q; ++i) { var sum = 0L; var d = pos[x[i]].d; if (d >= 2) { sum += slist[d - 2].Get(pos[plist[plist[x[i]]]].p); // Write($"+ {slist[d - 2].Get(pos[plist[plist[x[i]]]].p)}" ); slist[d - 2].Set(pos[plist[plist[x[i]]]].p, 0); } if (d >= 1) { var par = plist[x[i]]; sum += slist[d - 1].Get(pos[par].p); // Write($"+ {slist[d - 1].Get(pos[par].p)} "); slist[d - 1].Set(pos[par].p, 0); sum += slist[d].Prod(ref1[par].b, ref1[par].e); // Write($"+ {slist[d].Prod(ref1[par].b, ref1[par].e)} "); slist[d].Apply(ref1[par].b, ref1[par].e, 0); } else { sum += slist[d].Get(pos[x[i]].p); // Write($"+ {slist[d].Get(pos[x[i]].p)} "); slist[d].Set(pos[x[i]].p, 0); } sum += slist[d + 1].Prod(ref1[x[i]].b, ref1[x[i]].e); // Write($"+ {slist[d + 1].Prod(ref1[x[i]].b, ref1[x[i]].e)} "); slist[d + 1].Apply(ref1[x[i]].b, ref1[x[i]].e, 0); sum += slist[d + 2].Prod(ref2[x[i]].b, ref2[x[i]].e); // Write($"+ {slist[d + 2].Prod(ref2[x[i]].b, ref2[x[i]].e)} "); slist[d + 2].Apply(ref2[x[i]].b, ref2[x[i]].e, 0); // WriteLine($"= {sum}"); slist[d].Set(pos[x[i]].p, sum); ans[i] = sum; // for (var f = 0; f < slist.Length; ++f) // { // WriteLine($"dep = {f}"); // for (var g = 0; g < dlist[f].Count; ++g) Write($"({dlist[f][g]}, {slist[f].Get(g)}) "); // WriteLine(); // } } WriteLine(string.Join("\n", ans)); } static void CreateDList(int cur, int prev, int d, List[] tree, List> dlist, (int b, int e)[] ref1, (int b, int e)[] ref2, int[] plist, (int d, int p)[] pos) { while (d + 2 >= dlist.Count) dlist.Add(new List()); pos[cur] = (d, dlist[d].Count); dlist[d].Add(cur); var r1b = dlist[d + 1].Count; var r2b = dlist[d + 2].Count; foreach (var next in tree[cur]) { if (prev == next) continue; plist[next] = cur; CreateDList(next, cur, d + 1, tree, dlist, ref1, ref2, plist, pos); } ref1[cur] = (r1b, dlist[d + 1].Count); ref2[cur] = (r2b, dlist[d + 2].Count); } struct SegOp : ILazySegTreeOperator { public long Composition(long f, long g) { if (f == Id()) return g; return f; } public long E() => 0; public long Id() => -1; public long Mapping(long f, long x) { if (f == Id()) return x; return f; } public long Op(long a, long b) => a + b; } interface ILazySegTreeOperator { /// 集合S上の二項演算 S×S → S S Op(S a, S b); /// Sの単位元 S E(); /// 写像f(x) S Mapping(F f, S x); /// 写像の合成 f ○ g F Composition(F f, F g); /// 恒等写像 id F Id(); } // モノイドの型 S // 写像の型 F // 以下の関数を格納する T // ・: S × S → S を計算する関数 S op(S a, S b) // e を返す関数 S e() // f(x) を返す関数 S mapping(F f, S x) // f○gを返す関数 F composition(F f, F g) // idを返す関数 F id() // S,Fはreadonlyにしておくと速い // Tの関数オーバーフローに注意 class LazySegTree { int _n; int size; int log; List d; List lz; ILazySegTreeOperator op; public LazySegTree(int n, ILazySegTreeOperator op) { _n = n; var v = new S[n]; for (var i = 0; i < v.Length; ++i) v[i] = op.E(); Init(v, op); } public LazySegTree(S[] v, ILazySegTreeOperator op) { _n = v.Length; Init(v, op); } private void Init(S[] v, ILazySegTreeOperator op) { size = 1; log = 0; this.op = op; while (size < v.Length) { size <<= 1; ++log; } d = Enumerable.Repeat(op.E(), size * 2).ToList(); lz = Enumerable.Repeat(op. Id(), size).ToList(); for (var i = 0; i < v.Length; ++i) d[size + i] = v[i]; for (var i = size - 1; i >= 1; --i) Update(i); } /// 一点更新 public void Set(int pos, S x) { pos += size; for (var i = log; i >= 1; --i) Push(pos >> i); d[pos] = x; for (var i = 1; i <= log; ++i) Update(pos >> i); } /// 一点取得 public S Get(int pos) { pos += size; for (var i = log; i >= 1; --i) Push(pos >> i); return d[pos]; } /// 区間取得 op(a[l..r-1]) public S Prod(int l, int r) { if (l == r) return op.E(); l += size; r += size; for (var i = log; i >= 1; --i) { if (((l >> i) << i) != l) Push(l >> i); if (((r >> i) << i) != r) Push(r >> i); } S sml = op.E(); S smr = op.E(); while (l < r) { if ((l & 1) != 0) sml = op.Op(sml, d[l++]); if ((r & 1) != 0) smr = op.Op(d[--r], smr); l >>= 1; r >>= 1; } return op.Op(sml, smr); } /// 全体取得 op(a[0..n-1]) public S AllProd() => d[1]; /// なにこれ a[p] = op_st(a[p], x) public void Apply(int pos, F f) { pos += size; for (var i = log; i >= 1; --i) Push(pos >> i); d[pos] = op.Mapping(f, d[pos]); for (var i = 1; i <= log; ++i) Update(pos >> i); } /// 区間更新 i = l..r-1 について a[i] = op_st(a[i], x) public void Apply(int l, int r, F f) { if (l == r) return; l += size; r += size; for (var i = log; i >= 1; --i) { if (((l >> i) << i) != l) Push(l >> i); if (((r >> i) << i) != r) Push((r - 1) >> i); } { var l2 = l; var r2 = r; while (l < r) { if ((l & 1) != 0) AllApply(l++, f); if ((r & 1) != 0) AllApply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (var i = 1; i <= log; ++i) { if (((l >> i) << i) != l) Update(l >> i); if (((r >> i) << i) != r) Update((r - 1) >> i); } } /// segtreeの上で二分探索をする /// Sを引数にとりboolを返す関数gが必要 /// fが単調であれば、g(op(a[l], a[l + 1], ... a[r - 1])) = true となる最大のrが取得される /// 制約 /// ・fに副作用がない /// ・f(op.E()) = true /// public int MaxRight(int l, Predicate g) { if (l == _n) return _n; l += size; for (var i = log; i >= 1; --i) Push(l >> i); S sm = op.E(); do { while (l % 2 == 0) l >>= 1; if (!g(op.Op(sm, d[l]))) { while (l < size) { Push(l); if (g(op.Op(sm, d[l]))) { sm = op.Op(sm, d[l]); ++l; } } return l - size; } sm = op.Op(sm, d[l]); ++l; } while ((l & -l) != l); return _n; } /// segtreeの上で二分探索をする /// Sを引数にとりboolを返す関数gが必要 /// fが単調であれば、g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小のlが取得される /// 制約 /// ・fに副作用がない /// f(op.E()) = true public int MinLeft(int r, Predicate g) { if (r == 0) return 0; r += size; for (var i = log; i >= 1; --i) Push((r - 1) >> i); S sm = op.E(); do { --r; while (r > 1 && r % 2 == 1) r >>= 1; if (!g(op.Op(d[r], sm))) { while (r < size) { Push(r); r = (2 * r + 1); if (g(op.Op(d[r], sm))) { sm = op.Op(d[r], sm); --r; } } return r + 1 - size; } sm = op.Op(d[r], sm); } while ((r & -r) != r); return 0; } void Update(int k) { d[k] = op.Op(d[2 * k], d[2 * k + 1]); } void AllApply(int k, F f) { d[k] = op.Mapping(f, d[k]); if (k < size) lz[k] = op.Composition(f, lz[k]); } void Push(int k) { AllApply(2 * k, lz[k]); AllApply(2 * k + 1, lz[k]); lz[k] = op.Id(); } } }