合约数

发布时间: 2018年4月15日 22:29   最后更新: 2018年4月15日 23:24   时间限制: 2000ms   内存限制: 128M

在埃森哲,员工培训是最看重的内容,最近一年,我们投入了 9.41 亿美元用于员工培训和职业发展。截至 2018 财年末,我们会在全球范围内设立 100 所互联课堂,将互动科技与创新内容有机结合起来。按岗培训,按需定制,随时随地,本土化,区域化,虚拟化的培训会让你快速取得成长。小埃希望能通过培训学习更多ACM 相关的知识,他在培训中碰到了这样一个问题,

给定一棵$n$个节点的树,并且根节点的编号为$p$,第$i$个节点有属性值$val_i$, 定义$F(i)$: 在以$i$为根的子树中,属性值是$val_i$的合约数的节点个数。$y$ 是 $x$ 的合约数是指 $y$ 是合数且 $y$ 是 $x$ 的约数。小埃想知道$\sum_\limits{i=1}^n i · F(i)$对1000000007取模后的结果。

输入测试组数$T$,每组数据,输入$n+1$行整数,第一行为$n$和$p$,$1 \le n \le 20000$, $1 \le p \le n$, 接下来$n-1$行,每行两个整数$u$和$v$,表示$u$和$v$之间有一条边。第$n+1$行输入$n$个整数$val_1$, $val_2$,…, $val_n$,其中$1 \le val_i \le 10000$,$1 \le i \le n$.

对于每组数据,输出一行,包含1个整数表示$\sum_\limits{i=1}^n i · F(i)$对1000000007取模后的结果

复制
2
5 4
5 3
2 5
4 2
1 3
10 4 3 10 5
3 3
1 3
2 1
1 10 1
11
2

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛