树上博弈
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有一棵共有 n 个结点的有根树，规定 1 号节点为根节点。

除根结点外，每个结点都有一些金币。具体地，编号为 i 的结点上有 c_i 个金币（2 \leqslant i \leqslant n）。

游戏开始时，有一只棋子位于根节点，而后 Alice 和 Bob 轮流进行如下操作：

  • 将棋子从当前结点 x 移动到其任意一个子孙结点 y，并且该玩家获得结点 y 上所有的金币。

我们说结点 x 为结点 y 的子孙结点，是指 x \neq y 并且结点 y 位于从结点 x 到根结点的最短路径上。

当棋子位于叶子结点时无法继续进行操作，此时游戏结束。

记游戏结束时 Alice 有 a 个金币，Bob 有 b 个金币。

Alice 的目标是让 a - b 尽可能大，Bob 的目标则与之相反。

Alice 和 Bob 都很聪明，他们都会采取最优策略进行游戏。

现在由 Alice 先手开始游戏，请你预测游戏结束时 a - b 的值。

输入描述:

本题包含多组测试数据。

第一行一个整数 T (1 \leqslant T \leqslant {10}^5)，表示测试数据的数量。

对于每组测试数据：

\bullet 第一行有一个整数 n (2 \leqslant n \leqslant 2 \times {10}^5)，表示树的结点数量。
\bullet 第二行有 n - 1 个整数 c_2, c_3, \ldots, c_n (0 \leqslant c_i \leqslant {10} ^ 9)，表示结点 i 上有 c_i 个金币。
\bullet 第三行有 n - 1 个整数 p_2, p_3, \ldots, p_n (1 \leqslant p_i < i)，表示结点 i 的父结点为结点 p_i。

输入数据保证所有测试数据的 n 之和 \sum n \leqslant 2 \times {10}^5。

输出描述:

每组测试数据输出一行一个整数，表示游戏结束时 a - b 的值。
示例1

输入

复制 
5
5
2 3 4 5
1 2 3 4
5
5 1 1 1
1 2 3 4
5
5 4 3 1
1 2 3 4
5
520 114514 1919810 998244353
1 2 2 2
5
998244353 1919810 114514 520
1 2 2 2

输出

复制 
5
4
3
998244353
996324543