树上路径的最小公倍数之和

题目描述

给定一棵有 ( n ) 个节点的无根树，每个节点上有一个正整数权值 ( a_i )。

定义简单路径的价值为路径上所有节点权值的最小公倍数（LCM）。

请你计算树上所有不同的简单路径的价值之和。

由于答案可能非常大，请输出对 ( 10^9 + 7 ) 取模的结果。

输入格式

第一行一个整数 ( n )，表示树的节点数。

第二行 ( n ) 个整数，表示每个节点的权值 ( a_i )。

接下来 ( n-1 ) 行，每行两个整数 ( u ) 和 ( v )，表示节点 ( u ) 和 ( v ) 之间有一条无向边。

输出格式

输出一个整数，表示树上所有不同的简单路径的价值之和，对 ( 10^9 + 7 ) 取模。

样例输入

3
2 3 5
1 2
2 3

样例输出

61

样例解释

所有的简单路径及其价值为：

• 节点 1，价值 ( \mathrm{lcm}(2) = 2 )
• 节点 2，价值 ( \mathrm{lcm}(3) = 3 )
• 节点 3，价值 ( \mathrm{lcm}(5) = 5 )
• 路径 1-2，价值 ( \mathrm{lcm}(2,3) = 6 )
• 路径 2-3，价值 ( \mathrm{lcm}(3,5) = 15 )
• 路径 1-2-3，价值 ( \mathrm{lcm}(2,3,5) = 30 )

价值之和为 ( 2 + 3 + 5 + 6 + 15 + 30 = 61 )。

数据范围

• ( 1 \leq n \leq 10^5 )
• ( 1 \leq a_i \leq 10^6 )
• ( 1 \leq u, v \leq n )

输入样例

5
2 4 6 8 10
1 2
1 3
3 4
3 5

输出样例

330

luogu什么难度qwq