Tap here to switch tabs
Problem
Submissions

Problem: Count Valid Paths in a Tree

Try to solve the Count Valid Paths in a Tree problem.

Statement

Given an undirected tree with nn nodes labeled from 11 to n, you are provided with an integer n and a 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between node uiu_i and node viv_i.

A path between two nodes (u,v)(u, v) where u<vu < v is considered valid if the simple path connecting them contains exactly 11 prime number among the sequence of node values visited.

Return the total number of valid paths in the given tree.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 1≤ui,vi≤1 \leq u_i, v_i \leq n

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Valid Paths in a Tree

Try to solve the Count Valid Paths in a Tree problem.

Statement

Given an undirected tree with nn nodes labeled from 11 to n, you are provided with an integer n and a 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between node uiu_i and node viv_i.

A path between two nodes (u,v)(u, v) where u<vu < v is considered valid if the simple path connecting them contains exactly 11 prime number among the sequence of node values visited.

Return the total number of valid paths in the given tree.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 1≤ui,vi≤1 \leq u_i, v_i \leq n

  • The input is generated such that edges represents a valid tree.