题目描述

下方有简要题面。

北京的冬天下着大雪，虽然不是仲夏是深冬，但是小 T 还是想起了那年仲夏夜他做过的梦。

他梦到他在一棵以 $1$ 为根的有根树上，他的好朋友小 F 正在另一个节点上向他挥手。他把手伸了过去，由于两个人的手不够长，只有所在节点的深度差小于等于 $k$ 的时候，他们才能握到手。

手握紧以后，小 T 感受到一股神奇的能量从身体中传来，具体地说，每个点有三个属性 $a,b,c$ ，这股能量从 $u$ 流到 $v$ ，假设两个点的 $lca$ 为 $p$ ，那么能量的大小为 $a_{lca(u,v)} b_u c_v$ 。

小 T 只知道自己和小 F 都在某个点的子树内（废话），但是他忘了是哪个点了，请你求出对于 $x \in[1,n]$ ，如果两个点 $u,v$ 在 $x$ 的子树内，最大的能量值。

简要题面

给定一棵有 $n$ 个节点的有根树，根为 $1$ ，和序列 $a_i,b_i,c_i$ ，对于每个点 $x$ ，求：

$$\max_{(u,v) \in T(x)} [|dep_u - dep_v| \leq k] [u \neq v]\ a_{lca(u,v)} b_u c_v $$

其中 $T(x)$ 代表 $x$ 的子树。

输入格式

为了减小输入量，我们只输入树的形态， $a,b,c$ 序列将随机生成。

第一行两个整数 $n,k$ ，代表节点个数，距离限制。

第二行 $n - 1$ 个整数 $p_i$ ，$p_i$ 代表 $i + 1$ 号点在树上的父亲。

最后一行一个整数 $seed$ ，代表种子，$a,b,c$ 将由以下程序生成，请将下列片段加入你的代码，在输入完所有内容后调用 $getdata$ 函数：

unsigned int seed; //seed was already read.
inline unsigned int rnd()
{
    seed ^= seed >> 13;
    seed ^= seed << 17;
    seed ^= seed >> 5;
    return seed;
}
inline void getdata()
{
    for(int i = 1;i <= n;i++){
        a[i] = rnd() % 100000;
        b[i] = rnd() % 100000;
        c[i] = rnd() % 100000;
    }
};

输出格式

输出一行一个整数，假设 $ans_i$ 是 $i$ 的子树的答案，$cnt_0$ 为所有 $ans_i$ 中 $0$ 的个数，请输出 $(\oplus_{i = 1}^n ans_i) - cnt_0$ 。

输入样例#1

10 2
1 1 1 4 1 1 5 6 2 
1176046251

输出样例#1

101916155564591

样例解释

$a$ 数组：$[7408,61418,22221,50866,32588,10210,37976,58994,43842,87764]$

$b$ 数组：$[73313,73261,37568,36160,62889,70983,58983,29741,52653,39962]$

$c$ 数组：

$[99727,15431,11807,63957,82090,65935,37266,12726,86693,11189]$

$ans$ 数组：$[204592806725418,50345398912522,0,204592806725418,79561604029720,62829575325990,0,0,0,0]$

输入样例#2/输出样例#2

详见下发的 $dream2.in/dream2.out$。

此样例满足测试点 $3\sim 8$ 的限制。

输入样例#3/输出样例#3

详见下发的 $dream3.in/dream3.out$ 。

此样例满足测试点 $9 \sim 12$ 的限制。

输入样例#4/输出样例#4

详见下发的 $dream4.in/dream4.out$ 。

此样例满足测试点 $13 \sim 20$ 的限制。

数据范围

测试点编号	n $\leq$	k $\leq$
$1 \sim 2$	$1000$	$63$
$3 \sim 8$	$10^5$
$9 \sim 12$	$2 \times 10^6$	$5$
$13 \sim 20$		$63$