$$\mathsf{我的個人主頁}$$

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

• DFS 算法：記憶化搜索
• DFS 算法：全排列問題
• DFS 算法：洛谷B3625迷宮尋路

---

此系列更新頻繁，求各位讀者點贊
關注我可以了解更多內容哦
$偷偷告訴你，我正在沖1100粉$
$你們有什么想了解的可以發在評論區，我會仔細的看$
$1100粉時我會抓幾個做文章$

---

今天我們學什么

今天我們不學什么，就是做一道圖論DFS的題目

題目

題目描述

給定一棵樹，每個結點有一個整數權值，一開始每個結點均為黑色。

若相鄰兩個黑色結點的權值之和為質數，我們就可以把其中的一個結點變成紅色。問最多可以把多少個點變為紅色。

輸入格式

第一行一個整數 $n$，表示樹的結點數量。

第二行 $n$ 個整數 $a_1,?,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;
}

怎么樣，這是不是很簡單呢？

總結

有一些題是模板題，此時套上模板稍稍修改即可