2825. 传送门树

【题目描述】

有1棵n 个节点的树，节点编号为1 到n，i 号节点的权值为Wi。这棵树有些奇怪，它的每1个

叶子节点都有一个传送门可在到达根节点(即每个叶子节点与根节点之间有1条边权为0 的边)。

我们称这样的树为传送门树，根节点编号为1。我们需要最小化从u 到v 的路径(每条边只能经过1次) 上的节点权值之和，

并且在最小化节点权值之和的同时求这个路径上可能的最大权值。

【输入格式】

第一行两个整数n 和q，n 表示节点个数，q 表示询问个数。

第二行n - 1 个整数Ai，表示i + 1 号节点的父亲为Ai

第三行n 个整数Wi 表第i 号节点的权值为Wi

接下来q 行，每行两个整数u，v，表示1组询问

【输出格式】

对于每组询问输出两个整数x; y

x 表示u 到v 的权值和最小的路径的权值和，y 表示这条路径上点权最大值。如果有多个相同权值和的路径，输出那个点权最大值最大的。

【样例输入】

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

【样例输出】

1373 960

【数据范围】

对于30% 的数据，n <= 300，q <= 1000

对于50% 的数据，n <= 2000，q <= 10000

对于100% 的数据，n <= 100000，q <= 100000

【来源】

qbxt 2017.10.2 t3