首页 > 试题广场 >

多彩的树

[编程题]多彩的树

热度指数：2 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一棵树包含 N 个节点，节点编号从 1 到 N。节点总共有 K 种颜色，颜色编号从 1 到 K。第 i 个节点的颜色为 A_i。
F_i 表示恰好包含 i 种颜色的路径数量。请计算：
$\left( \sum _{ i=1 }^{ K }{ ({ F }_{ i } \times { 131 }^{ i }) } \right) { mod }({ 10 }^{ 9 }+7)$

输入描述:

第一行输入两个正整数 N 和 K，N 表示节点个数，K 表示颜色种类数量。
第二行输入 N 个正整数，A₁, A₂, A₃, ... ..., A_N，A_i 表示第 i 个节点的颜色。
接下来 N - 1 行，第 i 行输入两个正整数 U_i 和 V_i，表示节点 U_i 和节点 V_i 之间存在一条无向边，数据保证这 N-1 条边连通了 N 个节点。
1 ≤ N ≤ 50000.
1 ≤ K ≤ 10.
1 ≤ A_i ≤ K.