Tap here to switch tabs
Problem
Submissions

Problem: Count Valid Paths in a Tree

Count Valid Paths in a Tree asks you to count pairs of nodes whose connecting path visits exactly one node with a prime value, using the given tree edges.

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

Count Valid Paths in a Tree asks you to count pairs of nodes whose connecting path visits exactly one node with a prime value, using the given tree edges.

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.