P11690 [Ynoi Hard Round 2025] 《十字神名的预言者》理解（色彩）

   

> 棋如人生，落子无悔。步步思量，方能远航。 给定一棵 $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$ 作为根时的答案。

Idea：zhaohaikun，Solution：zhaohaikun，Code：zhaohaikun，Data：zhaohaikun。 对于所有数据满足：$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$ 连一条边。