小红在刷小红书的时候看到了一颗挂着小红薯的小红树，所以小红也想种一颗小红树挂一些小红薯发小红书。 小红有一颗树，每个结点有一个权值，初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点，如果它们都是白色且权值的和是质数，小红就可以选择其中一个节点染红。 小红想知道最多可以染红多少个节点？
区块链毕设网qklbishe.com为您提供问题的解答
小红在刷小红书的时候看到了一颗挂着小红薯的小红树，所以小红也想种一颗小红树挂一些小红薯发小红书。
小红有一颗树，每个结点有一个权值，初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点，如果它们都是白色且权值的和是质数，小红就可以选择其中一个节点染红。
小红想知道最多可以染红多少个节点？
import java.util.*; public class Main{ static List<Integer>[] g; static int[] w; static boolean[] vis; static Map<Integer,Boolean> map = new HashMap<>(); public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); g = new ArrayList[n + 1]; w = new int[n + 1]; vis = new boolean[n + 1]; Arrays.setAll(g, i -> new ArrayList<>()); for (int i = 1; i <= n; i++) { w[i] = sc.nextInt(); } for (int i = 0; i < n - 1; i++) { int u = sc.nextInt(), v = sc.nextInt(); g[u].add(v); g[v].add(u); } System.out.println(dfs(1 ,-1)); } private static int dfs(int node, int fa) { int ans = 0; for (Integer x : g[node]) { if(x == fa) continue; int num = w[x] + w[node]; if(!map.containsKey(num)) map.put(num, isPrime(num)); int temp = 0; if(map.get(num)){ if(!vis[node] && !vis[x]){ vis[node] = true; temp = dfs(x, node) + 1; vis[node] = false; } }else temp = dfs(x, node); ans += temp; } return ans; } private static boolean isPrime(int x) { if(x == 1) return false; if(x == 2) return true; for (int i = 2; i * i <= x; i++){ if(x % i == 0) return false; } return true; } }
28:40
以上就是关于问题小红在刷小红书的时候看到了一颗挂着小红薯的小红树，所以小红也想种一颗小红树挂一些小红薯发小红书。
小红有一颗树，每个结点有一个权值，初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点，如果它们都是白色且权值的和是质数，小红就可以选择其中一个节点染红。
小红想知道最多可以染红多少个节点？的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}