GCD树

p6.cpp

1000ms, 512MB

【题目描述】

现在给定一棵包含 $n$ 个点的、以 $T$ 号点为根的有根树，每个节点上有点权 $Vi$。 现在定义一个点 $u$ 的价值为：等概率随机选择点 $u$ 到树根 $T$ 路径上的任一点 $v$，点 $u$ 的价值为 $u$ 到 $v$ 路径上节点点权的最大公约数。 现在求这棵树上所有点价值和的期望，对 1,000,000,007 （1e9+7）取模。

【输入格式】

第一行两个正整数 $n, T$ ，表示点数和根节点编号。（$1 \le n \le 10^5,1 \le T \le n$) 第二行为 $n$ 个正整数，描述每个点的权值 $Vi$。($0 \le Vi \le 10^9$) 接下来 $n-1$ 行，每行两个整数 $u, v$，表示编号为 $u$ 的节点与编号为 $v$ 的节点之间有一条边。

【输出格式】

一行，一个整数，表示答案。 注意：对于分数 $\frac{A}{B}$，输出一个整数表示 $A*(B^{-1})$ 的结果, 其中 $B^{-1}$ 是 B 的逆元，即满足 $(B*B^{-1}) mod (10^9+7) = 1$

【样例】

【输入样例1】

3 1
3 6 2
1 2
1 3

【输出样例1】

9

【样例解释1】 对于样例1，树的价值有4种可能的形态。

点1、点2、点3的价值分别为{3,6,2}, {3,6,1}, {3,3,2}, {3,3,1}，相应价值和为11,10, 8, 7, 期望为9。

【输入样例2】

4 1
2 6 4 8
1 2
2 3
3 4

【输出样例2】

666666684

【数据规模与约定】

对于10%的数据：$n \le 8$ 对于30%的数据：$n \le 1000$ 对于额外20%的数据，保证树根为1号节点，且树边以($1 \rightarrow 2,2 \rightarrow 3,3 \rightarrow 4, ..., n-1 \rightarrow n$ ) 的形式给出。 对于100%的数据：$n \le 100,000$, 每个点的点权 $Vi \le 1,000,000,000$