题目描述
棋如人生,落子无悔。步步思量,方能远航。
给定一棵 n 个点的树,第 i 个节点有 bi 个棋子,且最多能放 ai 个棋子。现在有一个点 k 是根。每次操作你可以选择一个点,将它的一个棋子,移到它的父亲上,需要满足它父亲的棋子数没有超过限制,然后需要最小化每个棋子到 k 的距离和。
对 k=1,2,⋯,n 都求出答案。
输入格式
第一行包含一个正整数 n 表示树的结点数量。
第二行包含 n 个正整数,第 i 个正整数表示第 i 个结点上最多能放 ai 个棋子。
第三行包含 n 个正整数,第 i 个正整数表示第 i 个结点上初始放了 bi 个棋子。
接下来 n−1 行,每行两个数 u,v,表示树上的一条边。
输出格式
一行 n 个整数表示,第 i 个整数表示 i 做根时的答案。
样例输入 1
3
6 2 10
6 0 2
1 2
2 3
样例输出 1
2 6 0
样例输入 2
5
7 6 2 1 10
3 5 0 0 7
1 2
2 3
1 4
4 5
样例输出 2
10 12 20 14 9
样例 3
见选手目录下的 chess/chess3.in 与 chess/chess3.ans。
数据范围
对于所有数据满足:1≤n≤5×105,0≤bi≤ai,1≤ai≤107,为了避免答案爆 long long,将 ai 的范围开小了一点。
subtask 1(1 分):bi=0;
subtask 2(5 分):n≤2000;
subtask 3(11 分):n≤8000;
subtask 4(3 分):链,保证 ∀i∈[1,n−1]∩Z,满足 i 和 i+1 有边;
subtask 5(3 分):菊花,保证 ∀i∈[2,n]∩Z,满足 1 和 i 有边;
subtask 6(6 分):保证树随机;
subtask 7(16 分):ai≤5;
subtask 8(22 分):n≤5×104;
subtask 9(16 分):n≤105;
subtask 10(11 分):n≤2×105;
subtask 11(5 分):n≤3×105;
subtask 12(1 分):无。
这里说明随机树的生成方式:对于结点 i∈[2,n],在 [1,i−1] 内等概率随机一个点 p,将 i,p 连一条边。