题目内容

塔子哥是一个热爱冒险和探索的年轻人。有一天，他看到了一张神秘的照片，照片上有一颗挂着红薯的树。这个景象让塔子哥觉得非常有趣，他决定也要种一颗树，并挂上一些红薯，以此分享他的冒险故事。

思路

考虑对于树上两个相邻的白色节点，权值之和为质数，则可以选择一个点染色为红色。

考虑每条边，如果这条边对应的两个节点权值之和不为质数，则这条边就可以被断开。

所以，通过这样的断开后，我们只需要考虑每棵树，这些树上的每条边的两个节点权值之和均为质数。

考虑选择任意一个点作为树根，按照这种做法，每个树根的数量必然小于等于每个儿子的数量，所以对于每条边，我们都选择作为儿子的点。这样，有多少条边，就可以有多少个被染为红色的点。

另外，这里需要快速判断一个数是否为质数，可以用欧拉筛或埃氏筛法。欧拉筛是 $O(n)$ 的，埃氏筛法是 $O(n\log n)$