A4677 | $移动$

来源官方 / 2024

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制: 2S 空间限制: 512mb 样例文件: Move 小 T 有一棵 $n$ 个结点的树，初始时每个结点最多只有一枚棋子。 现在有一个结点 $k$ 是根。每次操作你可以选择一个结点，满足该结点有一枚棋子，将这枚棋子移到它的父亲结点上，需要满足它的父亲结点没有棋子，求最多移动次数。 如果没有棋子，则答案为 $0$。 对 $k=1,2,\cdots,n$ 都求出答案。

第一行一个正整数 $n$ 表示树的点数。 第二行一个长度为 $n$ 的 01 字符串 $s$，其中第 $i$ 个字符 $s$ 表示初始时，结点 $i$ 是否有棋子。如果 $s_i$ 为 1 ，则说明有，否则说明没有。 接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i, v_i$，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。

一行 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个点为根时的最多移动次数。

输入 #1

输出 #1

2 2 4 2 6 2

输入 #2

见选手目录下的 move/move2.in 与 move/move2.ans。

该组样例满足数据范围中描述的测试点 1 的限制。

输出 #2

输入 #3

见选手目录下的 move/move3.in 与 move/move3.ans。

该组样例满足数据范围中描述的测试点 4 的限制。

输出 #3

输入 #4

见选手目录下的 move/move4.in 与 move/move4.ans。

该组样例满足数据范围中描述的测试点 6 的限制。

输出 #4

输入 #5

见选手目录下的 move/move5.in 与 move/move5.ans。

该组样例满足数据范围中描述的测试点 13 的限制。

输出 #5

输入 #6

见选手目录下的 move/move6.in 与 move/move6.ans。

该组样例满足数据范围中描述的测试点 18 的限制。

输出 #6

输入 #7

见选手目录下的 move/move7.in 与 move/move7.ans。

该组样例满足数据范围中描述的测试点 20 的限制。

输出 #7

输入 #8

见选手目录下的 move/move8.in 与 move/move8.ans。

该组样例满足数据范围中描述的测试点 22 的限制。

输出 #8

对于所有的测试数据，保证： - $1 \leq n \leq 5\times 10^5$； - 对于任意的 $i(1 \leq i \leq n - 1)$，都有 $1 \leq u_i, v_i \leq n$，且构成一颗合法的树。 测试点编号$n\le$特殊性质$1\sim 3$$10$无$4,5$$300$无$6$$2000$无$7\sim 9$$7000$无$10\sim 12$$5\times 10^4$无$13\sim 16$$10^5$无$17$$3\times 10^5$无$18,19$$5\times 10^5$A$20,21$$5\times 10^5$B$22\sim 24$$5\times 10^5$C$25$$5\times 10^5$无 - 特殊性质 A：保证 $\forall i\in [1, n-1]\cap \mathbb{Z}$，满足 $i$ 和 $i+1$ 有边； - 特殊性质 B：保证 $\forall i\in [2, n]\cap \mathbb{Z}$，满足 $1$ 和 $i$ 有边； - 特殊性质 C：保证树的生成方式形如，对于结点 $i\in [2,n]$，在 $[1,i-1]$ 内等概率随机一个点 $p$，将 $i,p$ 连一条边。

C++ 编辑器

输入

输出