How hard is LeetCode 2867. Count Valid Paths in a Tree?

LeetCode 2867. Count Valid Paths in a Tree is rated Hard on LeetCode.

What is the time complexity of LeetCode 2867. Count Valid Paths in a Tree?

The Python solution on this page runs in O(n \times \alpha(n)).

What is the space complexity of LeetCode 2867. Count Valid Paths in a Tree?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2867. Count Valid Paths in a Tree cover?

LeetCode 2867. Count Valid Paths in a Tree is tagged Tree, Depth-First Search, Math, Dynamic Programming and Number Theory on LeetCode.

Count Valid Paths in a Tree — LeetCode 2867 Python Solution

HardTreeDepth-First SearchMathDynamic ProgrammingNumber Theory

Problem: #2867
Pattern: Tree Traversal
Reading time: 9 min
Source: leetcode.com

The problem

There is an undirected tree with n nodes labeled from 1 to n. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.

Example

Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]
Output: 4
Explanation: The pairs with exactly one prime number on the path between them are:

Python solution

Python

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


mx = 10**5 + 10
prime = [True] * (mx + 1)
prime[0] = prime[1] = False
for i in range(2, mx + 1):
    if prime[i]:
        for j in range(i * i, mx + 1, i):
            prime[j] = False


class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        uf = UnionFind(n + 1)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
            if prime[u] + prime[v] == 0:
                uf.union(u, v)

        ans = 0
        for i in range(1, n + 1):
            if prime[i]:
                t = 0
                for j in g[i]:
                    if not prime[j]:
                        cnt = uf.size[uf.find(j)]
                        ans += cnt
                        ans += t * cnt
                        t += cnt
        return ans

Complexity

Measure	Complexity
Time	O(n \times \alpha(n))
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2867. Count Valid Paths in a Tree is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2867. Count Valid Paths in a Tree?: LeetCode 2867. Count Valid Paths in a Tree is rated Hard on LeetCode.
What is the time complexity of LeetCode 2867. Count Valid Paths in a Tree?: The Python solution on this page runs in O(n \times \alpha(n)).
What is the space complexity of LeetCode 2867. Count Valid Paths in a Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2867. Count Valid Paths in a Tree cover?: LeetCode 2867. Count Valid Paths in a Tree is tagged Tree, Depth-First Search, Math, Dynamic Programming and Number Theory on LeetCode.