Transmigration tree

There is a tree, $n$ nodes, numbered from $1$ to $n$, each node has a weight, but each leaf node is the father of the root,

we call such a tree as Transmigration tree, The root of each tree is node $1$.

We need to minimize the sum of weights that node $u$ to node $v$ and know who is the biggest weights node in this path.

The first line of the input is a single integer $T (T \leq 10)$, indicating the number of testcases.

Then $T$ testcases follow.In each testcase,

The first line contains two integers $n,q$, the number of nodes and inquiry$(2 \leq n \leq 50000, 1 \leq q < 100000)$.

The second line contains $n - 1$ integers $A_i ( 1 \leq A_i \leq i )$ represent the node $i + 1$'s father is node $A_i$.

The third line contains $n$ integers $B_i ( 1 \leq i \leq n, 0 \leq B_i \leq 1000)$ represent the node $i$'s weight is $B_i$.

Then $q$ line follow,each line contains two integers $u,v$,it represents a query$(1 \leq u,v \leq n)$.

For each query,we should output one line "$x \ y$", where $x$ is the smallest the sum of weights that node $u$ to node $v$ and $y$ is the weight of the biggest weights node in this path.(If there are multiple paths, please calculating the maximum node weights largest)

1
5 1
1 2 3 4
413 127 263 869 960
1 5

1373 960

BestCoder Round #55 ($)