namespace Main{ int fa[N], son[N], ch[N][2]; ll tag[N]; inlinevoidcalc(int x){ CCF -= ans[x]; if (son[x]) ans[x] = 2 * (sum[x] - sum[son[x]]); //如果有"重"儿子 elseif (a[x] * 2 > sum[x] + 1) ans[x] = 2 * (sum[x] - a[x]); //如果自己点权过大 else ans[x] = sum[x] - 1; //没有点权过大的点或子树 CCF += ans[x]; } voiddfs(int x){ sum[x] = a[x]; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa[x]) continue; fa[y] = x; dfs(y); sum[x] += sum[y]; if (!son[x] || sum[son[x]] < sum[y]) son[x] = y; } if (sum[son[x]] * 2 <= sum[x] + 1) son[x] = 0; calc(x); ch[x][1] = son[x]; } inlinevoidpushdown(int x){ if (!x || !tag[x]) return; if (ch[x][0]) { tag[ch[x][0]] += tag[x]; sum[ch[x][0]] += tag[x]; } if (ch[x][1]) { tag[ch[x][1]] += tag[x]; sum[ch[x][1]] += tag[x]; } tag[x] = 0; } inlineboolisroot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x; } inlinevoidrotate(int x){ int y = fa[x], z = fa[y], k = (ch[y][1]==x); if (!isroot(y)) ch[z][ch[z][1]==y] = x; fa[x] = z; ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y; ch[x][!k] = y; fa[y] = x; } int stk[N], top; inlinevoidsplay(int x){ stk[top=1] = x; for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i]; while (top) pushdown(stk[top--]); while (!isroot(x)) { int y = fa[x], z = fa[y]; if (!isroot(y)) ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y); rotate(x); } } inlineintfindroot(int x){ while (ch[x][0]) pushdown(x), x = ch[x][0]; return x; } voidaccess(int x, int v){ a[x] += v; for (int i = 0; x; i = x, x = fa[x]) { splay(x); sum[x] += v; if (ch[x][0]) sum[ch[x][0]] += v, tag[ch[x][0]] += v; //给重链上的祖先打标记 //要打标记是因为没有makeroot,没法用split把路径分割出来 //只能通过把重链打上标记来加 if (son[x]) { stk[top=1] = son[x]; for (int j = son[x]; !isroot(j); j = fa[j]) stk[++top] = fa[j]; while (top) pushdown(stk[top--]); //pushdown确保sum[son[x]]的值正确 if (sum[son[x]] * 2 <= sum[x] + 1) ch[x][1] = 0, son[x] = 0; //判断还有没有"重"儿子 } int F = findroot(i); //找到轻子树的深度最小的节点 //它的sum才是整棵轻子树的sum if (sum[F] * 2 > sum[x] + 1) ch[x][1] = F, son[x] = F; //找到新的"重"儿子 calc(x); //更新答案 } } voidsolve(){ dfs(1); printf("%lld\n", CCF); for (int i = 1, x, w; i <= m; i++) { read(x); read(w); access(x, w); printf("%lld\n", CCF); } } }
intmain(){ read(n); read(m); for (int i = 1; i <= n; i++) read(a[i]); for (int i = 1, u, v; i < n; i++) { read(u); read(v); addedge(u, v); } Main::solve(); return0; }