题目描述

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

• 由 $-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$ 。

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