Define a particular type of arrays as perfect if:
- Consisting of -1 and 1;
- The sum of any of its prefix is not less than 0;
- The sum of the entire array is 0.
For example, the following arrays are perfect:
- 1 1 1 -1 -1 -1
- 1 -1 1 1 -1 -1
While the followings are not:
The NP-value of a perfect array is the maximum prefix sum occurred in the array. For example, the NP-values of the two perfect arrays above are 3 and 2 respectively.
Given a tree with either -1 or 1 assigned on each node, please figure out a simple path, that the array concatenated by values on the path is perfect along with the maximum NP-value.
输入描述:
The input consists of multiple test cases.
Each test case begins with an integer n (1 ≤ n ≤ 106), the number of nodes in the tree.
Then n lines follow. The i-th line of the following n lines consists of fi (0 ≤ fi ≤ n) and vi (vi ∈ {-1, 1}), which respectively denotes the parent node and the assigned value of the i-th node. Nodes are labeled from 1 to n, and fi = 0 indicates that node i is a root.
The sum of n in all test cases does not exceed 5 × 106.
输出描述:
For each test case, output the maximum NP-value found on the tree. Output 0 if such path doesn't exist.