Tree Imbalance Minimization

You are given a row of T undirected rooted trees (each tree’s root is numbered 1). Each edge in a tree carries a weight m_i. The tree’s edges are given in a fixed order, so the children of any node have a predetermined left‐to‐right order. For each tree, your task is to compute its imbalance defined as follows:

For a rooted tree, choose a shortest path from the root to any leaf (this will be called the main path). Remove all edges on this main path. Then every remaining edge belongs to a branch off the main path. At each node u on the main path (except the leaf), let the ordered list of u’s children be given as they appear in the input. Let the child that continues the main path be at index j. For every other child, consider the entire branch rooted at that child (including the edge connecting u to that child and all edges in its subtree). The branches whose connection appears before index j are assigned to the left group and those after index j are assigned to the right group. The imbalance for the chosen main path is the absolute difference between the total weights of all edges in the left group and right group. The imbalance of a single node (with no edges) is defined as 0.

Your answer for a tree is the minimum imbalance among all possible choices of a root‐to‐leaf main path.

Note: Each tree is provided in the following format. The weight-sum of an empty set is defined to be 0.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 10), the number of trees. For each tree, the first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes. Then n-1 lines follow. The i-th line (for i from 2 to n) contains two integers p and m separated by a space, where p (1 ≤ p < i) denotes the parent of node i and m (1 ≤ m ≤ 10⁴) is the weight of the edge between node p and node i. The order of the edges for a node is the order in which they appear in the input.

outputFormat

For each tree, output a single integer on a separate line, representing the minimum imbalance of that tree.

sample

1
1

0