小红在刷小红书的时候看到了一颗挂着小红薯的小红树,所以小红也想种一颗小红树挂一些小红薯发小红书。 小红有一颗树,每个结点有一个权值,初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点,如果它们都是白色且权值的和是质数,小红就可以选择其中一个节点染红。 小红想知道最多可以染红多少个节点?

区块链毕设网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链游项目方科学家脚本开发培训

从业7年-专注一级市场


微信:btc9767
TELEGRAM :https://t.me/btcok9

具体资料介绍

web3的一级市场千万收益的逻辑


进群点我



qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红在刷小红书的时候看到了一颗挂着小红薯的小红树,所以小红也想种一颗小红树挂一些小红薯发小红书。 小红有一颗树,每个结点有一个权值,初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点,如果它们都是白色且权值的和是质数,小红就可以选择其中一个节点染红。 小红想知道最多可以染红多少个节点?