4081. 魔法试练场

【题目描述】

        魔法师小A要参加一场试练，试练场有n个试练点，在每个试练点可以获得一个魔法值（非负整数），这n个试练点由n-1条路连通，任意两点通过这n-1条路可互达。

        小A可以从任意一点出发，沿一条试练路径进行试练，每个点只能经过并试练一次，。定义一条试练路径的魔法值（小A通过该路径所获魔法值）为路径上的所有试练点所获魔法值之和与该路径上的最大试练点魔法值的差值。

        给定参数P,我们想知道，有多少不同的试练路径，满足它的魔法值恰好是P的倍数。注意：单点算作一个路径；u≠v时，(u,v)和(v,u)只算一次。

【输入格式】

第一行包含两个整数n,P;意义见题面描述。

接下来n-1行，每行两个整数u、v,表示一条连接两个试练点的路。

接下来一行n个整数，第i个整数val;表示试练点i的魔法值。

【输出格式】

输出包含一行一个整数，表示答案。

【样例输入】

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

【样例输出】

9

【样例说明】

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

大样例

【数据规模与约定】

对所有测试点，我们有：

n≤10⁵,P≤10⁷,val≤10^9。

每个测试点的数据特性：

测试点   n        性质

1~2    ≤2000      A

3~6    ≤2000      无

7~14   ≤10⁵        A

15~19  ≤105        B

20~25   ≤10⁵       无

性质A:保证任一试练点最多连接2条路。

性质B:试练场为树的形态，数据通过以某个点为根，其他点依次"随机父亲"生成。数据有一定梯度。

【来源】

在此键入。