#R1001. 大根堆

    ID: 23 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>图论树上启发式合并数据结构线段树

大根堆

题目描述

给定一棵 nn 个节点的有根树,编号依次为 11nn,其中 11 号点为根节点。每个点有一个权值 viv_i。 你需要将这棵树转化成一个大根堆。确切地说,你需要选择尽可能多的节点,满足大根堆的性质:对于任意两个点 i,ji,j,如果 ii 在树上是 jj 的祖先,那么 vi>vjv_i>v_j。 请计算可选的最多的点数,注意这些点不必形成这棵树的一个连通子树。

格式

输入格式

第一行包含一个正整数 nn,表示节点的个数。 接下来 nn 行,每行两个整数 vi,piv_i,p_i,表示每个节点的权值与父亲。

输出格式

输出一行一个正整数,即最多的点数。

数据样例

6
3 0
1 1
2 1
3 1
4 1
5 1
5

数据规模与约定

$1\leq n\leq 200000,0\leq v_i\leq 10^9,1\leq p_i< i,p_1=0$

Problem from BZOJ4919.