// #include using namespace std; #define ll long long #define int long long #define pii pair #define fi first #define se second #define rep(i, x, y) for (int i = (x); i <= (y); i ++ ) #define per(i, x, y) for (int i = (x); i >= (y); i -- ) const int N = 5e5 + 5, M = 1e6 + 5; const int inf = 1e9, mod = 998244353; const ll INF = 1e18, RMX = 2324814; mt19937 rd(time(0)); uniform_int_distribution dist(0, RMX); int n, a[N]; vector fvv[N], g[N]; struct segment{ int tr[N << 2], laz[N << 2]; void pushup(int now){ tr[now] = tr[now << 1] + tr[now << 1 | 1]; } void pushdown(int now){ if (laz[now]) tr[now << 1] = 0, laz[now << 1] = 1, tr[now << 1 | 1] = 0, laz[now << 1 | 1] = 1, laz[now] = 0; } void modify_clr(int now, int l, int r, int lt, int rt){ if (lt <= l && r <= rt){ tr[now] = 0, laz[now] = 1; return ; } pushdown(now); int mid = (l + r) >> 1; if (lt <= mid) modify_clr(now << 1, l, mid, lt, rt); if (mid < rt) modify_clr(now << 1 | 1, mid + 1, r, lt, rt); pushup(now); } void modify_pt(int now, int l, int r, int pos, int x){ if (l == r){ tr[now] = x; return ; } pushdown(now); int mid = (l + r) >> 1; if (pos <= mid) modify_pt(now << 1, l, mid, pos, x); else modify_pt(now << 1 | 1, mid + 1, r, pos, x); pushup(now); } int query(int now, int l, int r, int lt, int rt){ if (lt <= l && r <= rt) return tr[now]; pushdown(now); int mid = (l + r) >> 1; if (rt <= mid) return query(now << 1, l, mid, lt, rt); if (mid < lt) return query(now << 1 | 1, mid + 1, r, lt, rt); return query(now << 1, l, mid, lt, rt) + query(now << 1 | 1, mid + 1, r, lt, rt); } } seg; int pos[N], id[N], tot, fa[N], dep[N]; void dfs(int f, int u){ dep[u] = dep[f] + 1, fa[u] = f; fvv[dep[u]].push_back(u); for (auto v : g[u]){ if (v == f) continue; dfs(u, v); } } int mn1[N], mx1[N]; int mn2[N], mx2[N]; signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; rep(i, 1, n - 1){ int u, v; cin >> u >> v; u ++, v ++ ; g[u].push_back(v); g[v].push_back(u); } rep(i, 1, n) cin >> a[i]; dfs(0, 1); rep(i, 1, n) mn1[i] = mn2[i] = inf, mx1[i] = mx2[i] = -inf; rep(i, 1, n){ for (auto u : fvv[i]) pos[u] = ++ tot, id[tot] = u; } rep(u, 1, n){ if (fa[u]) mn1[fa[u]] = min(mn1[fa[u]], pos[u]); if (fa[fa[u]]) mn2[fa[fa[u]]] = min(mn2[fa[fa[u]]], pos[u]); if (fa[u]) mx1[fa[u]] = max(mx1[fa[u]], pos[u]); if (fa[fa[u]]) mx2[fa[fa[u]]] = max(mx2[fa[fa[u]]], pos[u]); seg.modify_pt(1, 1, n, pos[u], a[u]); } int q; cin >> q; while (q -- ){ int u; cin >> u; u ++ ; vector rg; if (mn1[u] <= mx1[u]) rg.push_back({mn1[u], mx1[u]}); if (mn2[u] <= mx2[u]) rg.push_back({mn2[u], mx2[u]}); if (fa[u]){ rg.push_back({pos[fa[u]], pos[fa[u]]}); if (mn1[fa[u]] <= mx1[fa[u]]) rg.push_back({mn1[fa[u]], mx1[fa[u]]}); } if (fa[fa[u]]) rg.push_back({pos[fa[fa[u]]], pos[fa[fa[u]]]}); int sum = 0; for (auto qwq : rg){ int l = qwq.fi, r = qwq.se; sum += seg.query(1, 1, n, l, r); } for (auto qwq : rg){ int l = qwq.fi, r = qwq.se; seg.modify_clr(1, 1, n, l, r); } seg.modify_pt(1, 1, n, pos[u], sum); cout << sum << "\n"; } } //\ 这个题目就是说,距离 x 为 1, 2 的点的值之和为 ans,然后将这些点的值清零,x 的值设为 ans 即可\ 然后考虑 x 距离为 1 就是,x 的子节点 + x 的父节点\ 距离为 2 就是,x 的子树中 dep = dep[x] + 2 的点,fa[x] 的所有子节点,fa[fa[x]]\ 然后我们考虑用一种方法使得这些东西构成连续区间\ 疑似层序遍历即可。\