/ TYWZ / 题库 /

2019.2.10 Problem B - control

2019.2.10 Problem B - control

题目描述

给定一棵含\(n\)个点的有根树,点的编号为\(1 \sim n\),其中1号点为根节点,每条边分别有一个正整数边权。
定义\(\text{dist}(u,v)\)为从点\(u\)到点\(v\)的简单路径上所有边的权值之和。每个点设有一个正整数阈值\(a_i, i = 1 \cdots n\),对于两个点\(v,u(u \ne v)\),若\(v\)是\(u\)的祖先,且\(\text{dist}(u,v) \leq a_u\),则称点\(v\)“控制”了点\(u\)。
请你按照编号顺序依次输出每个节点控制了其他多少个点。

输入格式

第一行一个整数\(n\),表示树上点的个数;
第二行\(n\)个整数\(a_1,a_2 \cdots a_n\),依次表示每个点的阈值;
下面\(n-1\)行,每行包含两个整数\(f_i, w_i, i = 2 \cdots n\),依次表示\(i\)号点的父亲为\(f_i\),它与父亲间边的权值为\(w_i\)。

输出格式

\(n\)个非负整数,依次表示\(1 \sim n\)号点所控制的点的个数。两个数之间用恰好1个空格隔开。

样例

输入

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

输出

1 0 1 0 0

数据规模、时空限制

对于30%的数据,\(n \leq 2000\)
对于另外的20%数据,\(i\)号点的父亲必然是\(i-1\)号点,\(i=2 \cdots N\)
对于100%的数据,\(1 \leq n \leq 2 \times {10}^5, \quad 1 \leq p_i \leq n, \quad 1 \leq a_i, w_i \leq {10}^9\)
时间限制1s,空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人:于剑

信息

难度
10
分类
树结构 点击显示
标签
(无)
递交数
1
已通过
0
通过率
0%
上传者