运筹帷幄 - 题目

题目描述

棋如人生，落子无悔。步步思量，方能远航。

给定一棵 $n$ 个结点的树，第 $i$ 个结点有 $b_i$ 个棋子，且最多能放 $a_i$ 个棋子。现在有一个结点 $k$ 是根。每次操作你可以选择一个结点，将它的一个棋子，移到它的父亲上，需要满足它父亲的棋子数没有超过限制，然后需要最小化所有棋子到 $k$ 的距离和。

对 $k=1,2,\cdots,n$ 都求出答案。

第一行包含一个正整数 $n$ 表示树的结点数量。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个结点上最多能放 $a_i$ 个棋子。

第三行包含 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个结点上初始放了 $b_i$ 个棋子。

接下来 $n-1$ 行，每行两个数 $u,v$，表示树上的一条边。

一行 $n$ 个整数表示，第 $i$ 个整数表示 $i$ 做根时的答案。

2 6 0

10 12 20 14 9

见选手目录下的 $\texttt{chess/chess3.in}$ 与 $\texttt{chess/chess3.ans}$。

对于所有数据满足：$1\le n\le 5\times 10^5$，$0 \le b_i \le a_i$，$1\le a_i\le 10^7$，为了避免答案爆 long long，将 $a_i$ 的范围开小了一点。

subtask 1（$1$ 分）：$b_i=0$；

subtask 2（$5$ 分）：$n\le 2000$；

subtask 3（$11$ 分）：$n\le 8000$；

subtask 4（$3$ 分）：链，保证 $\forall i\in [1, n-1]\cap \mathbb{Z}$，满足 $i$ 和 $i+1$ 有边；

subtask 5（$3$ 分）：菊花，保证 $\forall i\in [2, n]\cap \mathbb{Z}$，满足 $1$ 和 $i$ 有边；

subtask 6（$6$ 分）：保证树随机；

subtask 7（$16$ 分）：$a_i\le 5$；

subtask 8（$22$ 分）：$n\le 5\times 10^4$；

subtask 9（$16$ 分）：$n\le 10^5$；

subtask 10（$11$ 分）：$n\le 2\times 10^5$；

subtask 11（$5$ 分）：$n\le 3\times 10^5$；

subtask 12（$1$ 分）：无。

这里说明随机树的生成方式：对于结点 $i\in [2,n]$，在 $[1,i-1]$ 内等概率随机一个点 $p$，将 $i,p$ 连一条边。