题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

3
1 2
1 3
4 5
2 4 
6 10

输出样例

2

提示

数据范围

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

对于$\red{100\%}$的数据，$\red{n<=5\times10^4,1≤}$$\red{l_i≤}$$\red{r_i≤}$$\red{10^9}$