#2228. 有要求的树

有要求的树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一棵包含n\red{n}个节点1,...,n)\red{(1,...,n)}的有根树,1\red{1 }为根节点,节点x\red{x}的父节点表示为px.\red{p_x.} 这棵树上的每一个节点x\red{x}的初始权值为0,\red{0,}现在想让聪明的你按照如下操作要求在这棵树上 增加点权,使得每个点x\red{x}上的权值vx\red{v_x}符合lx\red{l_x≤}vx\red{v_x≤}rx.\red{r_x.}

对于每一次操作: 选择从根节点1\red{1}到节点x\red{x}的一条路径,让它们分别增加非负的权值c1,...,cx\red{c_1,...,c_x}且满足这一次 操作中对于任意一个节 点x\red{x}增加的权值cx\red{c_x}不小于其父节点Px\red{P_x}增加的权值Cpi.\red{C_{p_i}.}

最少需要多少次这样的操作呢?

输入格式

第一行输入一个n\red{n,}表示节点个数;

第二行开始有n1\red{n-1}个输入,每行两个数字,节点 i,p\red{i,p} 。表示pi\red{p,i}有一条边

后面n\red{n}行每一行包含两个整数Ii,ri\red{I_i,r_i}表示节点i\red{i}对应的可能的权值的上下边界。.

输出格式

输出一个整数表示最少需要的操作次数。

样例

输入样例

3
1 2
1 3
4 5
2 4 
6 10

输出样例

2

提示

数据范围

对于20%\red{20\%}的数据,这棵树是一条链;

对于100%\red{100\%}的数据,n<=5×104,1\red{n<=5\times10^4,1≤}li\red{l_i≤}ri\red{r_i≤}109\red{10^9}

普及组测试2题目重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-7-30 16:30
结束于
2022-7-31 16:30
持续时间
24 小时
主持人
参赛人数
18