P17814 [ICPC 2019 Nanchang R] Tree

考虑一棵有 $n$ 个顶点的有根树，其中第一个顶点为根。第 $i$ 个顶点被赋予了权值 $v_i$。 现在给定一个正整数 $k$。一个有序顶点对 $(x,y)$（表示树中的第 $x$ 个和第 $y$ 个顶点）被称为合法的，当且仅当它满足以下条件： - $x\neq y$； - 第 $x$ 个顶点不是第 $y$ 个顶点的祖先； - 第 $y$ 个顶点不是第 $x$ 个顶点的祖先； - 连接这两个顶点的最短路径长度不超过 $k$； - 取这两个顶点的最近公共祖先的权值，记作 $v_z$。则 $v_x+v_y=2v_z$。 你能计算出这棵树中合法顶点对的总数吗？

第一行包含两个整数 $n$ 和 $k$ $(1 \le n, k \le 10^5)$，含义如上所述。 第二行包含 $n$ 个整数，其中第 $i$ 个整数为第 $i$ 个顶点的权值 $v_i$ $(0 \le v_i \le n)$。 第三行包含 $n-1$ 个整数，其中第 $i$ 个整数表示第 $(i+1)$ 个顶点的父顶点的编号。 我们保证给定的树确实是一棵树。

在一行中输出合法顶点对的数量。 若 $x_1=x_2$ 且 $y_1=y_2$，则认为 $(x_1,y_1)$ 与 $(x_2,y_2)$ 是相同的对。

翻译由 DeepSeek V4 Pro 完成