B 合约数

链接：https://www.nowcoder.com/acm/contest/91/B
来源：牛客网

题目描述

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

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

输入描述:

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

输出描述:

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

示例1

输入

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

备注:

n>=10000的有20组测试数据

dfs问题，先预处理下10000之内的每个合约数，然后从根节点p开始遍历，每次删除前面出现的合约数，等回溯后就加上当前的合约数，这样就可以得到当前的合约数了。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int mod = 1000000007;
 7 const int M = 20010;
 8 vector<int> vs[M], H[M];
 9 bool vis[M];
10 int val[M], F[M], ans, cnt[M];
11 void init() {
12     vis[0] = vis[1] = true;
13     for(int i = 2; i <= 100; i ++) {
14         if(!vis[i]) {
15             for(int j = i*i; j <= 10000; j += i) vis[j] = true;
16         }
17     }
18     for(int i = 4; i <= 10000; ++ i) {
19         if(vis[i]) {
20             for(int j = 4; j <= i; ++ j) {
21                 if(vis[j] && i%j == 0) H[i].push_back(j);
22             }
23         }
24     }
25 }
26 void dfs(int u) {
27     for(int i = 0; i < H[val[u]].size(); i ++) {
28         F[u] -= cnt[H[val[u]][i]];
29     }
30     cnt[val[u]]++;
31     for(int i = 0; i < vs[u].size(); i ++) {
32         if(!vis[vs[u][i]]) {
33             vis[vs[u][i]] = 1;
34             dfs(vs[u][i]);
35         }
36     }
37     for(int i = 0; i < H[val[u]].size(); i ++) {
38         F[u] += cnt[H[val[u]][i]];
39     }
40     ans += 1LL*F[u]*u;
41     ans %= mod;
42 }
43 int main() {
44     init();
45     //printf("%d
",H[10].size());
46     int t, n, p;
47     cin >> t;
48     while(t--) {
49         memset(vis,0,sizeof(vis));
50         memset(F,0,sizeof(F));
51         memset(cnt,0,sizeof(cnt));
52         for(int i = 0; i <= M; i ++) vs[i].clear();
53         ans = 0;
54         cin >> n >> p;
55         for(int i = 0; i < n-1; i ++) {
56             int u, v;
57             cin >> u >> v;
58             vs[u].push_back(v);
59             vs[v].push_back(u);
60         }
61         for(int i = 1; i <= n; i ++) cin >> val[i];
62         vis[p] = 1;
63         dfs(p);
64         cout << ans << endl;
65     }
66     return 0;
67 }