会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路
对于树上的每条边，若其连接的两个路由器的关键值之和为素数，则这条边是一条安全链路。因此，我们只需遍历所有边，对满足条件的边进行计数即可。
快速判断一个数是否为素数可以用欧拉筛或埃氏筛。欧拉筛是 O(n) 的，埃氏筛法是 O(nlogn)。
时间复杂度：O(n)
代码
题目内容
在一个由 n 个路由器组成的树形网络中，每个路由器 i 具有一个关键值 vi。定义一条链路为“安全链路”，当且仅当它连接的两个路由器的关键值之和为素数。请计算这棵树中安全链路的总数。
约束条件：
- 路由器数量 n 满足 1≤n≤105。
- 关键值 vi 满足 1≤vi≤105。
- 链路由 n−1 条边组成，保证构成一棵连通树。
输入描述
第一行包含一个整数 n，表示路由器数量。
