QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100
[+10]

# 9534. 运筹帷幄

统计

题目描述

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

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

k=1,2,,n 都求出答案。

输入格式

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

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

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

接下来 n1 行,每行两个数 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.inchess/chess3.ans

数据范围

对于所有数据满足:1n5×1050biai1ai107,为了避免答案爆 long long,将 ai 的范围开小了一点。

subtask 1(1 分):bi=0

subtask 2(5 分):n2000

subtask 3(11 分):n8000

subtask 4(3 分):链,保证 i[1,n1]Z,满足 ii+1 有边;

subtask 5(3 分):菊花,保证 i[2,n]Z,满足 1i 有边;

subtask 6(6 分):保证树随机;

subtask 7(16 分):ai5

subtask 8(22 分):n5×104

subtask 9(16 分):n105

subtask 10(11 分):n2×105

subtask 11(5 分):n3×105

subtask 12(1 分):无。

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