题号：NC207420
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
这里有一棵树，每个点和每条边都存在一个价值。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。
求这颗树上最大的点对价值为多少。点对至少需要两个点。
输入描述:
输入t，代表有t组样例。每组样例第一行输入n，代表有n个点。接下来有n-1行，第i行有a[i]和b[i]，代表a[i]节点与i节点存在一条边，且边的值为b[i]，2<=i<=n。接下来一行有n个值c[j]，代表每个节点j的价值，1<=j<=n。
（t<=10，n>1，n<1e6，a[i]<i，-500<=b[i]<=500，-500<=c[j]<=500）
输出描述:
输出最大的点对价值
示例1
输入
复制
1
4
1 -2
1 2
1 3
2 -2 3 4