#PQJ1822x9534. QOJ 1822_9534

    ID: 2717 传统题 2000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测贪心

QOJ 1822_9534

标题: 运筹帷幄 / 《十字神名的预言者》理解(色彩) - Problem - QOJ.ac

#9534. 运筹帷幄 / 《十字神名的预言者》理解(色彩)

Statistics

题目描述

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

给定一棵 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 连一条边。