#P17814. [ICPC 2019 Nanchang R] Tree
[ICPC 2019 Nanchang R] Tree
题目描述
考虑一棵有 个顶点的有根树,其中第一个顶点为根。第 个顶点被赋予了权值 。
现在给定一个正整数 。一个有序顶点对 (表示树中的第 个和第 个顶点)被称为合法的,当且仅当它满足以下条件:
- ;
- 第 个顶点不是第 个顶点的祖先;
- 第 个顶点不是第 个顶点的祖先;
- 连接这两个顶点的最短路径长度不超过 ;
- 取这两个顶点的最近公共祖先的权值,记作 。则 。
你能计算出这棵树中合法顶点对的总数吗?
输入格式
第一行包含两个整数 和 ,含义如上所述。
第二行包含 个整数,其中第 个整数为第 个顶点的权值 。
第三行包含 个整数,其中第 个整数表示第 个顶点的父顶点的编号。
我们保证给定的树确实是一棵树。
输出格式
在一行中输出合法顶点对的数量。
若 且 ,则认为 与 是相同的对。
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 完成