网络叶子 网站推广,做一手房做那个网站好,wordpress做app,成都网站快速排名软件目录 2867. 统计树中的合法路径数目
题目描述#xff1a;
实现代码与思路#xff1a;
筛质数 DFS
原理思路#xff1a; 2867. 统计树中的合法路径数目
题目描述#xff1a; 给你一棵 n 个节点的无向树#xff0c;节点编号为 1 到 n 。给你一个整数 n 和一个长度为 …目录 2867. 统计树中的合法路径数目
题目描述
实现代码与思路
筛质数 DFS
原理思路 2867. 统计树中的合法路径数目
题目描述 给你一棵 n 个节点的无向树节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges 其中 edges[i] [ui, vi] 表示节点 ui 和 vi 在树中有一条边。
请你返回树中的 合法路径数目 。
如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数那么我们称路径 (a, b) 是 合法的 。
注意
路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列序列中的节点 互不相同 且相邻节点之间在树上有一条边。路径 (a, b) 和路径 (b, a) 视为 同一条 路径且只计入答案 一次 。 示例 1 输入n 5, edges [[1,2],[1,3],[2,4],[2,5]]
输出4
解释恰好有一个质数编号的节点路径有
- (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
- (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
- (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
- (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
只有 4 条合法路径。示例 2 输入n 6, edges [[1,2],[1,3],[2,4],[3,5],[3,6]]
输出6
解释恰好有一个质数编号的节点路径有
- (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
- (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
- (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
- (1, 6) 因为路径 1 到 6 只包含一个质数 3 。
- (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
- (3, 6) 因为路径 3 到 6 只包含一个质数 3 。
只有 6 条合法路径。提示
1 n 105edges.length n - 1edges[i].length 21 ui, vi n输入保证 edges 形成一棵合法的树。
实现代码与思路
筛质数 DFS
class Solution {private final static int N (int)1e5 10;// 构建图邻接表int[] h new int[N], e new int[N * 2], ne new int[N * 2];int idx;boolean[] np new boolean[N 1]; // 筛选质数// 筛选1 ~ n 之中的质数public void getPrimes() {np[1] true;for (int i 2; i * i N; i) {if (!np[i]) { // 若是质数向后利用其筛选for (int j i * i; j N; j i) {np[j] true; // 被筛掉}}}} // 连接边public void add(int a, int b) {e[idx] b; ne[idx] h[a]; h[a] idx;}public long countPaths(int n, int[][] edges) {getPrimes();Arrays.fill(h, -1);// 加边for (int i 0; i edges.length; i) {int a edges[i][0];int b edges[i][1];add(a, b);add(b, a);}long res 0;int[] st2 new int[n 1]; // 记忆化搜索判断是否已经计算过以此节点为头的子树中非质数的个数for (int cur 1; cur n; cur) {if (np[cur]) continue; // 起始头不遍历非质数System.out.println(cur);int sum 0; // 以当前节点为头各个子树中非质数的节点和for (int i h[cur]; i ! -1; i ne[i]) {int j e[i];if (!np[j]) continue; // 不遍历质数if (st2[j] 0) { // 以非指数节点开头记忆化搜索记录下来个数ListInteger nodes new ArrayListInteger();dfs(j, -1, nodes);for (int t: nodes) {st2[t] nodes.size();}}res (long) st2[j] * sum; // 和以及遍历计算出的结点和相乘计算非质数与非质数经过一个质数的路径sum st2[j];}res sum; // 加上头节点开始的路径}return res;}// dfspublic void dfs(int x, int fa, ListInteger nodes) {nodes.add(x);for (int i h[x]; i ! -1; i ne[i]) {int j e[i];if (j ! fa np[j]) {dfs(j, x, nodes);}}}
}
原理思路 筛选出质数建图以质数开始向外遍历一次找到其非质数的子树dfs计算每个子树的非质数个数通过计算算出此质数相连的所有路径。最终算出全部符合条件的路径个数。详见代码。
