4023. 硝华流焰

【题目背景】

「霞彩焕花火，花火知我愿，我愿入夜空，夜空自甄明。」

【题目描述】

宵宫正在往一颗树上悬挂烟花。这颗树是一棵 $n$ 个节点、$n-1$ 条边构成的无根树。

宵宫会在每颗节点悬挂一个烟花盒，共有三种不同的烟花盒，分别记为 $0, 1, 2$ 三种型号。

树上每条边都有一个边权。宵宫认为，树上一条路径 $R(u, v)$ 的权值为路径上所有边的边权和。

她会告诉你每个节点悬挂烟花盒的类型，请你告诉她这颗树上所有包含全部三种型号的烟花盒的路径的权值和。

注意：在本题中，我们认为 $R(u, v)$ 与 $R(v, u)$ 是相同的。

【输入格式】

第一行一个正整数 $n$，表示树上的节点数。

第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，分别表示每个节点的烟花盒的类型。

以下 $n - 1$ 行，每行三个不同的正整数 $u_i, v_i, w_i$，表示一条连接 $u_i, v_i$，权值为 $w_i$ 的边。

【输出格式】

一行一个整数，表示所有包含全部三种型号的烟花盒的路径的权值和。答案对 $10^9 + 7$ 取模。

【样例1输入】

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

【样例1输出】

9

【样例1说明】

符合要求的路径只有 $R_{1, 3}$ 和 $R_{3, 4}$ 两条，权值和为 $3+6=9$.

【样例下载】

样例下载

【数据规模与约定】

对于所有数据，$1\leq n\leq 10^5,1\leq u_i,v_i\leq n,a_i\in \{0,1,2\},1\leq w\leq 10^3$。

【来源】

2024年校际联合邀请赛 入门组-第3场 Task4