塔子哥的树-小红书2024笔试(codefun2000)

题目链接
塔子哥的树-小红书2024笔试(codefun2000)

题目内容

塔子哥是一个热爱冒险和探索的年轻人。有一天，他看到了一张神秘的照片，照片上有一颗挂着红薯的树。这个景象让塔子哥觉得非常有趣，他决定也要种一颗树，并挂上一些红薯，以此分享他的冒险故事。
塔子哥收集了一颗神奇的数树种子，这颗数树与普通树不同，每个结点都有一个特殊的权值。初始时，所有节点都是白色的。塔子哥发现每次可以选择两个相邻的白色节点，并且它们的权值之和必须是质数。一旦满足这个条件，塔子哥就可以选择其中一个节点染成红色。
现在，塔子哥想知道，在这颗数树上，最多可以染红多少个节点。

输入描述

输出描述

输出一个整数表示正确答案。

样例1

输入

4
1 2 3 4
1 2
2 3
3 4

输出

3

提示

这题要使用无向边建立树，如果使用单向边建立会出现问题，比如1 2,3 2是两条边，如果使用单向边，建立的树就会出现节点2有2个根，分别是1和3。因此，不能用单向边建立树

题解1

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, a[N], ans=0;
vector<int> edge[N];

bool isPrime(int x){
	for(int i = 2; i <= x/i; i++){
		if(x%i == 0) return false;
	}
	return true;
}
void dfs(int u, int fa){
	int sz = edge[u].size();
	for(int j = 0; j < sz; j++){
		int v = edge[u][j];
		if(v == fa) continue;
		dfs(v, u);
		if(isPrime(a[u] + a[v])) { // 子节点与父节点之和是质数，将子节点染成红色，ans累加1即可 
			ans++;
		}
	}
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1, u, v; i < n; i++){
		scanf("%d%d", &u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,-1);
	printf("%d\n", ans);
	return 0;
}