Prime Path

4.2

8 votes
Algorithms, Depth First Search, C++, Graphs
Problem

Given a tree with N nodes numbered 1 to N and N1 edges, rooted at node 1. Find the number of unordered pair of distinct vertices (i,j) such that there exists exactly one prime number on the simple path between vertex i and j.

Note:

  • We only need to consider unordered pairs i.e. (i,j) and (j,i) are counted once.
  • The values of nodes in the path will be the node numbers.

Input format

  • The first line contains N denoting the number of vertices in the tree.
  • The next N1 lines contain two space-separated integers uv denoting an edge between vertex u and v.

Output format

Print a single integer, denoting the number of such pairs (i,j).

Constraints

1N1051u,vN

 

Sample Input
7
1 2
1 3
2 6
3 4
3 5
4 7
Sample Output
7
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 7 such possible paths:

  • 12
  • 13
  • 26
  • 126
  • 34
  • 47
  • 134
Editor Image

?