33OJ
登录 注册

#P17814. [ICPC 2019 Nanchang R] Tree

[ICPC 2019 Nanchang R] Tree

题目描述

考虑一棵有 nn 个顶点的有根树,其中第一个顶点为根。第 ii 个顶点被赋予了权值 viv_i。

现在给定一个正整数 kk。一个有序顶点对 (x,y)(x,y)(表示树中的第 xx 个和第 yy 个顶点)被称为合法的,当且仅当它满足以下条件:

  • x≠yx\neq y;
  • 第 xx 个顶点不是第 yy 个顶点的祖先;
  • 第 yy 个顶点不是第 xx 个顶点的祖先;
  • 连接这两个顶点的最短路径长度不超过 kk;
  • 取这两个顶点的最近公共祖先的权值,记作 vzv_z。则 vx+vy=2vzv_x+v_y=2v_z。

你能计算出这棵树中合法顶点对的总数吗?

输入格式

第一行包含两个整数 nn 和 kk (1≤n,k≤105)(1 \le n, k \le 10^5),含义如上所述。

第二行包含 nn 个整数,其中第 ii 个整数为第 ii 个顶点的权值 viv_i (0≤vi≤n)(0 \le v_i \le n)。

第三行包含 n−1n-1 个整数,其中第 ii 个整数表示第 (i+1)(i+1) 个顶点的父顶点的编号。

我们保证给定的树确实是一棵树。

输出格式

在一行中输出合法顶点对的数量。

若 x1=x2x_1=x_2 且 y1=y2y_1=y_2,则认为 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2) 是相同的对。

3 2
1 2 3
1 1
0
3 1
2 1 3
1 1
0
3 2
2 1 3
1 1
2

提示

翻译由 DeepSeek V4 Pro 完成