CF1714G Path Prefixes

# Path Prefixes 现有一颗以 $1$ 为根的树，节点编号从 $1$ 到 $n$ . 每条边有两个权值，分别为 $a_j$ 和 $b_j$ . 输出 $n-1$ 个数 $r_2,r_3 \cdots ,r_n$ ，其中 $r_i$ 定义如下: 考虑从根节点( $1$ 号节点 ) 到第 $i$ 号节点 $(2 \le i \le n)$ 的路径，令沿该路径 $a_j$ 的花费为 $A_i$ ， $r_i$ 为该路径的最长前缀，使该前缀的 $b_j$ 之和不大于 $A_i$ .  以 $n=9$ 时为例，如上图，蓝色数字表示 $a_j$ 的花费，红色数字表示 $b_j$ 的花费. 在这种情况下： - $ r_2=0 $ ， 因为到节点 $ 2 $ 的路径中有 $ a_j=5 $ ， 只有前缀为 $ 0 $ 时才可能有较小（或相等）的 $ b_j $ ； - $ r_3=3 $ ， 因为到节点 $ 3 $ 的路径中 $ a_j $ 为 $ 5+9+5=19 $ ， 长为 $ 3 $ 的前缀使 $ b_j $ 为 $ 6+10+1=17 $ ( $ 17 \le 19 $ 符合题意 )； - $ r_4=1 $ ， 因为到节点 $ 4 $ 的路径中 $ a_j $ 为 $ 5+9=14 $ ， 长为 $ 1 $ 的前缀使 $ b_j $ 为 $ 6 $ (这是最长的符合题意的前缀， 因为长为 $ 2 $ 的前缀的 $ b_j $ 为 $ 6+10=16 $ ， 大于 $ 14 $ )； - $ r_5=2 $ ， 因为到节点 $ 5 $ 的路径中 $ a_j $ 为 $ 5+9+2=16 $ ， 长为 $ 2 $ 的前缀使 $ b_j $ 为 $ 6+10=16 $ (这是最长的符合题意的前缀， 因为长为 $ 3 $ 的前缀的 $ b_j $ 为 $ 6+10+1=17 $ ， 比 $ 16 $ 大 )； - $ r_6=1 $ ， 因为到节点 $ 6 $ 的路径中 $ a_j $ 为 $ 2 $ ， 长为 $ 1 $ 的前缀使 $ b_j $ 等于 $ 1 $ ； - $ r_7=1 $ ， 因为到节点 $ 7 $ 的路径中 $ a_j $ 为 $ 5+3=8 $ ， 长为 $ 1 $ 的前缀使 $ b_j $ 等于 $ 6 $ (这是最长的符合题意的前缀， 因为长为 $ 2 $ 的前缀的 $ b_j $ 为 $ 6+3=9 $ ， 超出了期望的 $ 8 $ )； - $ r_8=2 $ ， 因为到节点 $ 8 $ 的路径中 $ a_j $ 为 $ 2+4=6 $ ， 长为 $ 2 $ 的前缀使 $ b_j $ 为 $ 1+3=4 $ ； - $ r_9=3 $ ， 因为到节点 $ 9 $ 的路径中 $ a_j $ 为 $ 2+4+1=7 $ ， 长为 $ 3 $ 的前缀使 $ b_j $ 为 $ 1+3+3=7 $ . 在第二组样例中 - $ r_2=0 $ ，因为到节点 $ 2 $ 的路径中 $ a_j $ 等于 $ 1 $ ， 只有前缀为 $ 0 $ 时才可能有较小（或相等）的 $ b_j $ - $ r_3=0 $ ， 因为到节点 $ 3 $ 的路径中 $ a_j $ 为 $ 1+1=2 $ ， 长为 $ 1 $ 的前缀使 $ b_j $ 等于 $ 100 $ ( $ 100 > 2 $ )； - $ r_4=3 $ ， 因为到节点 $ 4 $ 的路径中 of $ a_j $ 为 $ 1+1+101=103 $ ， 长为 $ 3 $ 的前缀使 $ b_j $ 为 $ 102 $ .

无

无

The first example is clarified in the statement. In the second example: - $ r_2=0 $ , since the path to $ 2 $ has an amount of $ a_j $ equal to $ 1 $ , only the prefix of this path of length $ 0 $ has a smaller or equal amount of $ b_j $ ; - $ r_3=0 $ , since the path to $ 3 $ has an amount of $ a_j $ equal to $ 1+1=2 $ , the prefix of length $ 1 $ of this path has an amount of $ b_j $ equal to $ 100 $ ( $ 100 > 2 $ ); - $ r_4=3 $ , since the path to $ 4 $ has an amount of $ a_j $ equal to $ 1+1+101=103 $ , the prefix of length $ 3 $ of this path has an amount of $ b_j $ equal to $ 102 $ , .