Skip to content

14233: 【原4233】穿越异世界

题目

题目描述

author: 泰玛什 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4233

Background

你在马路上遇到了车祸,醒来时发现自己穿越到了异世界。

Description

异世界有着森严的等级制度,人与人之间有着明确的上下级关系。为了简单起见,我们可以把所有人从1到n编号,并将他们的关系看做一棵树。

除了一号节点为根节点以外,每个点都有一个父节点,表示自己的直接上级。同时,由于不同人之间的关系不同,每个点和父节点的连边上都有边权\(w_i\),表示两点之间的亲近程度。

由于这样的等级制度,每个点都有一部分自己可以支配的人,对于第i号点,若第j号点被i支配,当且仅当:

  1. j在i的子树中

  2. j和i之间的距离\(d_{i,j}\)满足:\(d_{i,j} \leq a_j\),其中\(a_j\)为第j个人的威信值。

现在,为了在异世界活下去,请你计算出每个人可以支配的人的数量。

Input Format

第一行有一个整数\(n\),表示总人数。

接下来一行,一共\(n\)个数,\(a_1,a_2,...,a_n\)。

接下来\(n-1\)行,每行2个数。其中第i行包括两个整数\(p_i, w_i\)分别表示第i+1个点的父节点编号,以及它和父节点的亲近程度。

Output Format

输出共一行,n个数表示第i个。

Sample Input

5
2 5 1 4 6
1 7
1 1
3 5
3 6

Sample Output

1 0 1 0 0

Limit

  • 对于30%的数据,满足\(1 \leq n \leq 1000\)

  • 对于60%的数据,满足树是随机生成。

  • 对于100%的数据,满足\(1 \leq n \leq 2*10^5, 1 \leq a_i \leq 10^9, 1 \leq p_i \leq n, 1 \leq w_i \leq 10^9 \)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!