树上路径

树上路径

Description

给一棵 n 个节点的无根树,每个节点有个非负整点权,定义一条路径的价值为路径上的 (点权和)-(最大点权值)
给定参数 p ,求有多少条不同的简单路径满足它的价值恰好为 p 的倍数。
注意,单点也算做一个路径,u!=v 时, u->vv->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训练题

信息

难度
9
分类
树的分治 点击显示
标签
(无)
递交数
7
已通过
3
通过率
43%
上传者