图论DFS：黑红树

[img]https://i-blog.csdnimg.cn/blog_migrate/53d454b46f0e4ed423fbc59aa79ba6e1
.png#pic_center[/img]

                                                                       我的个人主页                                                             {\large \mathsf{{\color{Red} 我的个人主页} } }                        我的个人主页
                                                         往                                                 {\color{Red} {\Huge 往} }                  往                                                         期                                                 {\color{Green} {\Huge 期} }                  期                                                         文                                                 {\color{Blue} {\Huge 文} }                  文                                                         章                                                 {\color{Orange} {\Huge 章}}                  章

• DFS 算法&#xff1
  a;记忆化搜刮
  
• DFS 算法&#xff1
  a;全排列题目
  
• DFS 算法&#xff1
  a;洛谷B3625迷宫寻路
  

---

此系列更新频仍，求各位读者点赞
关注我可以相识更多内容哦
                                                         偷偷告诉你，我正在冲                               1
1
00                               粉                                                 {\color{Gray} {\small 偷偷告诉你，我正在冲1
1
00粉} }                  偷偷告诉你，我正在冲1
1
00粉
                                                         你们有什么想相识的可以发在批评区，我会仔细的看                                                 {\color{Gray} {\small 你们有什么想相识的可以发在批评区，我会仔细的看} }                  你们有什么想相识的可以发在批评区，我会仔细的看
                                                         1
1
00                               粉时我会抓几个做文章                                                 {\color{Gray} {\small1
1
00粉时我会抓几个做文章} }                  1
1
00粉时我会抓几个做文章

---

  
今天我们学什么

今天我们不学什么，就是做一道图论DFS的题目
题目

题目描述

给定一棵树，每个结点有一个整数权值，一开始每个结点均为黑色。
若相邻两个黑色结点的权值之和为质数，我们就可以把其中的一个结点变成红色。问最多可以把多少个点变为红色。
输入格式

第一行一个整数                                    n                              n                  n，表现树的结点数量。
第二行                                    n                              n                  n 个整数                                              a                            1
                                  ,                         ⋯                          ,                                   a                            n                                       a_1
, \cdots, a_n                  a1
​,⋯,an​，表现每个结点的权值。
接下来的                                    n                         −                         1
                              n-1
                  n−1
行，每行两个整数                                    x                         ,                         y                              x,y                  x,y，表现结点                                    x                         ,                         y                              x,y                  x,y 之间有一条边。
输出格式

一个整数，表现最多可以把多少个点变为红色。
样例 #1


样例输入 #1

1. 3
2. 1
3. 2 3
4. 1
5. 3
6. 1
7. 2

复制代码

样例输出 #1

1. 1

复制代码

提示

测试点编号                                                  n                                          n                           n                                                               a                                     i                                                      a_i                           ai​1
,2                                                  1
                                  ≤                                  n                                  ≤                                  20                                          1
\le n\le 20                           1
≤n≤20                                                  1
                                  ≤                                               a                                     i                                              ≤                                  1
00                                          1
\le a_i\le 1
00                           1
≤ai​≤1
003,4                                                  1
                                  ≤                                  n                                  ≤                                  1
000                                          1
\le n\le 1
000                           1
≤n≤1
000                                                  1
                                  ≤                                               a                                     i                                              ≤                                  1
000                                          1
\le a_i\le 1
000                           1
≤ai​≤1
0005,6,7                                                  1
                                  ≤                                  n                                  ≤                                  1
                                               0                                     5                                                      1
\le n\le 1
0^5                           1
≤n≤1
05                                                  1
                                  ≤                                               a                                     i                                              ≤                                  1
                                               0                                     5                                                      1
\le a_i\le 1
0^5                           1
≤ai​≤1
058,9,1
0                                                  1
                                  ≤                                  n                                  ≤                                  3                                  ×                                  1
                                               0                                     5                                                      1
\le n\le 3\times 1
0^5                           1
≤n≤3×1
05                                                  1
                                  ≤                                               a                                     i                                              ≤                                  1
                                               0                                     6                                                      1
\le a_i\le 1
0^6                           1
≤ai​≤1
06 题解

思绪

简单的图论DFS模板题目，稍稍修改模板即可
代码

1. #include <bits/stdc++.h>using namespace std;const int N&#61
2. ;300005;vector<int> G[N];int value[N],ans,n;bool visited[N];bool is_prime[2000005];void dfs(int step){        int now&#61
3. ;value[step];        visited[step]&#61
4. ;true;        for(auto a:G[step])        {                if(!visited[a])                {                        int temp&#61
5. ;value[a];                        if(is_prime[temp+now])                        {                                ans++;                        }                        dfs(a);                }        }}int main(){        memset(is_prime,true,sizeof(is_prime));        is_prime[0]&#61
6. ;is_prime[1
7. ]&#61
8. ;false;        for(int i&#61
9. ;2; i<&#61
10. ;2000000; i++)        {                if(is_prime[i])                {                        for(int j&#61
11. ;2; i*j<&#61
12. ;2000000; j++)                        {                                is_prime[i*j]&#61
13. ;false;                        }                }        }        cin>>n;        for(int i&#61
14. ;1
15. ; i<&#61
16. ;n; i++)        {                cin>>value[i];        }        for(int i&#61
17. ;1
18. ; i<n; i++)        {                int x,y;                cin>>x>>y;                G[x].push_back(y);                G[y].push_back(x);        }        for(int i&#61
19. ;1
20. ; i<&#61
21. ;n; i++)        {                if(!visited[i])                {                        dfs(i);                }        }        cout<<ans;        return 0;}

复制代码

怎么样，这是不是很简单呢&#xff1
f;
总结

有一些题是模板题，此时套上模板稍稍修改即可

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。