#6383. 「是男人就过8题——Pony.ai」PerfectNPArray

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

我们定义满足如下条件的数列是完美的:

  • -1 1 组成。
  • 它的任一前缀和都不小于 0
  • 数列的各项和为 0

下面列出一些完美的数列作为例子:

  • 1, 1, 1, -1, -1, -1
  • 1,-1,1,1,-1,-1

而如下的数列则不完美:

  • -1,1
  • 1,-1,-1,1

一个完美数列的 NP 值是这个数列的前缀和中最大的那个的值。比如,前文提到的两个完美数列的 NP 值分别为 3 2

给一棵树,这棵树的每个节点都被赋予了一个权值 -1 1 ,请找出一条简单路径,使得由这个路径上各点权值组成的数列是完美数列,且这个数列的 NP 值最大。

输入格式

输入包含多个测试数据。

每个测试数据第一行是一个整数 n ,代表这棵树有 n 个节点。

接下来有 n 行,第 i 行有两个用空格分开的数字 f_i v_i ( v_i \in \{-1,1\} ) ,表示第 i 个点的父节点和第 i 个点的权值。节点被编号为 1 n ,如果 f_i=0 ,那么节点 i 是这棵树的根。

输出格式

对于每个测试数据,输出每棵树的最大 NP 值,如果这样的路径不存在,输出 0

样例

样例输入

5
0 -1
1 1
1 -1
2 1
2 -1

样例输出

2

数据范围与提示

对于 100\% 的数据, 1 \leq n \leq 10^6 ,且每个测试点所有测试数据的 n 的总和不会超过 5 \times 10^6

特别鸣谢楼天城和吉如一提供试题,数据。