元宝 LeetCode 2867. 统计树中的合法路径数目 Java实现

LeetCode 2867「统计树中的合法路径数目 / Count Valid Paths in a Tree」思路是用埃氏筛预处理[1, 1e5]的质数枚举每个质数节点作为路径中间点向四周 DFS 走只经过合数节点的连通块记大小为sz对每个质数答案 各连通块大小之和质数↔合数路径 两两连通块大小乘积之和合数↔合数经此质数路径以下是可直接提交的 Java 实现class Solution { private static final int MAX 100_001; private static final boolean[] isPrime new boolean[MAX]; static { // 埃氏筛isPrime[i]true 表示 i 是质数 for (int i 2; i MAX; i) isPrime[i] true; for (int i 2; i * i MAX; i) { if (isPrime[i]) { for (int j i * i; j MAX; j i) { isPrime[j] false; } } } } public long countPaths(int n, int[][] edges) { // 建邻接表 ListInteger[] g new ArrayList[n 1]; for (int i 0; i n; i) g[i] new ArrayList(); for (int[] e : edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); } // blockSize[v] 0 表示该合数节点所属连通块大小记忆化 int[] blockSize new int[n 1]; long ans 0; // 枚举每个质数节点作为路径中间点 for (int p 1; p n; p) { if (!isPrime[p]) continue; long sum 0; // 已累计的合数连通块大小之和 for (int nb : g[p]) { if (isPrime[nb]) continue; // 不能经过别的质数 if (blockSize[nb] 0) { // 未访问过的合数连通块DFS 求大小 ListInteger comp new ArrayList(); dfs(nb, p, g, comp); for (int node : comp) blockSize[node] comp.size(); } ans sum * blockSize[nb]; // 两侧不同合数块两两配对 sum blockSize[nb]; } ans sum; // 质数本身 ↔ 各合数节点一端为质数 } return ans; } // DFS 收集从 cur 出发只经过合数节点的连通块 private void dfs(int cur, int parent, ListInteger[] g, ListInteger comp) { comp.add(cur); for (int nxt : g[cur]) { if (nxt ! parent !isPrime[nxt]) { dfs(nxt, cur, g, comp); } } } }复杂度筛法 O(N log log N)DFS 每个合数节点只访问一次整体 O(n)。如有不清楚的地方可以继续问