3666. B - 给树染色
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给出一棵带权值的树，最开始的时候每个节点都是白色 若相邻两个节点都是白色且权值之和为质数则可以将其中一个节点染成黑色 请你计算最多能将多少个节点染成黑色？ ## 输入格式 第一行输入一个正整数 $ n $ 代表节点的数量 第二行输入 $ n $ 个正整数 $ a_i $ 代表每个节点的权值 最后 $ n-1 $ 行输入这个树 $ 1\len\le3\cdot10^5 $ $ 1\lea_i\le10^6 $ ## 输出格式 输出染成黑色节点的数量 ## 输入 ```in1 3 1 2 3 1 2 1 3 ``` ## 输出 ```out1 1 ``` ```in2 7 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 3 6 3 7 ``` ```out2 6 ``` ## 提示 **【样例 1 解释】** 因为 $ a_1+a_2=3 $ ，是一个质数，所以我们可以把 $ 1 $ 染色，或者把 $ 2 $ 染色。（不能同时染黑）