图论DFS：黑红树

$$\mathsf{我的个人主页}$$

$往$ $期$ $文$ $章$

• DFS 算法：记忆化搜索
• DFS 算法：全排列问题
• DFS 算法：洛谷B3625迷宫寻路

---

此系列更新频繁，求各位读者点赞
关注我可以了解更多内容哦
$偷偷告诉你，我正在冲1100粉$
$你们有什么想了解的可以发在评论区，我会仔细的看$
$1100粉时我会抓几个做文章$

---

今天我们学什么

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

题目

题目描述

给定一棵树，每个结点有一个整数权值，一开始每个结点均为黑色。

若相邻两个黑色结点的权值之和为质数，我们就可以把其中的一个结点变成红色。问最多可以把多少个点变为红色。

输入格式

第一行一个整数 $n$，表示树的结点数量。

第二行 $n$ 个整数 $a_1,\cdots ,a_n$，表示每个结点的权值。

接下来的 $n-1$ 行，每行两个整数 $x,y$，表示结点 $x,y$ 之间有一条边。

输出格式

一个整数，表示最多可以把多少个点变为红色。

样例 #1

样例输入 #1

3
1 2 3
1 3
1 2

样例输出 #1

1

提示

测试点编号	$n$	$a_i$
1,2	$1\le n\le 20$	$1\le a_i\le 100$
3,4	$1\le n\le 1000$	$1\le a_i\le 1000$
5,6,7	$1\le n\le 10^5$	$1\le a_i\le 10^5$
8,9,10	$1\le n\le 3\times 10^5$	$1\le a_i\le 10^6$

题解

思路

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

代码

#include <bits/stdc++.h>
using namespace std;
const int N=300005;
vector<int> G[N];
int value[N],ans,n;
bool visited[N];
bool is_prime[2000005];
void dfs(int step)
{
int now=value[step];
visited[step]=true;
for(auto a:G[step])
{
if(!visited[a])
{
int temp=value[a];
if(is_prime[temp+now])
{
ans++;
}
dfs(a);
}
}
}
int main()
{
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2; i<=2000000; i++)
{
if(is_prime[i])
{
for(int j=2; i*j<=2000000; j++)
{
is_prime[i*j]=false;
}
}
}
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>value[i];
}
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
{
if(!visited[i])
{
dfs(i);
}
}
cout<<ans;
return 0;
}

怎么样，这是不是很简单呢？

总结

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

原文地址：https://blog.csdn.net/Python_enjoy/article/details/145225564

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！