树上路径
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训练题