Description

给一棵 n 个节点的无根树，每个节点有个非负整点权，定义一条路径的价值为路径上的 (点权和)-(最大点权值)
给定参数 p ，求有多少条不同的简单路径满足它的价值恰好为 p 的倍数。
注意，单点也算做一个路径，u!=v 时, u->v 和 v->u 算作一条路径。
简单路径就是不经过重复点的一条路径。

Input

第一行包含两个数 n,p;
接下来 n-1 行，每行两个数表示那两个点之间有一条树边;
接下来一行 n 个整数 (v[1]~v[n])，表示点 i 的权值.

Output

就一个数，表示答案

Sample Input

5 2
1 2
1 3
2 4
3 5
1 3 3 1 2

Sample Output

9

Limitation

n <= 10^5
p <= 10^7
v[i] <= 10^9

Hint

满足条件的路径有:
(1,1), (2,2), (3,3), (4,4), (5,5), (1,4), (2,3), (2,5), (3,5)

Source

GF训练题