[R29F]好树 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定一棵包含 $n$ 个节点的树和一个长度为 $n$ 的数组 $d$。

你需要为树上的每一个节点 $u$ 赋予一个整数权值，记作 $A_u$。称一种赋值方案是好的，当且仅当它满足以下两个条件：

1. 对于任意节点 $u$，其权值必须在 $[1, n]$ 的范围内，即 $1 \leq A_u \leq n$。
2. 对于树上的任意一条边 $(u, v)$，两个端点权值的差的绝对值必须满足：$|A_u - A_v| \leq d_u + d_v$。

对于每一种好的的赋值方案，需要计算其所有节点的权值和的平方和。

形式化地，设 $\mathbb{S}$ 是所有合法赋值方案的集合，你需要计算：

$$\sum_{S \in \mathbb{S}} \left( \sum_{u=1}^{n} A_{S,u} \right)^2 \bmod{P}$$

其中 $A_{S,u}$ 表示在方案 $S$ 中节点 $u$ 的权值。

由于答案可能很大，请将最终结果对给定的模数 $P$ 取模。

格式

输入格式

第一行包含两个整数 $n, P$，分别表示树的节点数量和模数。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $d_i$。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示树上的一条边。

输出格式

输出一个整数，表示题目所求的最终值对 $P$ 取模后的结果。

样例

样例输入 #1

2 1000000
1 1
1 2

样例输出 #1

38

样例解释 #1

约束条件为 $|A_1 - A_2| \leq d_1 + d_2 = 1 + 1 = 2$。

故所有可能的赋值方案 $(A_1, A_2)$ 如下：

• $(1, 1)$： $|1-1|=0 \leq 2$。合法。权值和为 $1+1=2$。平方为 $2^2=4$。
• $(1, 2)$： $|1-2|=1 \leq 2$。合法。权值和为 $1+2=3$。平方为 $3^2=9$。
• $(2, 1)$： $|2-1|=1 \leq 2$。合法。权值和为 $2+1=3$。平方为 $3^2=9$。
• $(2, 2)$： $|2-2|=0 \leq 2$。合法。权值和为 $2+2=4$。平方为 $4^2=16$。

所有赋值方案都满足条件，所以共有 $4$ 种合法的赋值方案。

故所有方案的权值和的平方和为 $4 + 9 + 9 + 16 = 38$。

样例输入 #2

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

样例输出 #2

630525

数据规模

对于 $20\%$ 的数据，$1\leq n \leq 6$。

对于 $60\%$ 的数据，$1 \leq n \leq 300$。

对于 $100\%$ 的数据，$1\leq n \leq 2000$，$1 \leq d_i \leq n$，$2 \leq P \leq 10^9$。