- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have an integer k and also have a tree with n nodes, we have to count the number of distinct pairs of vertices which have a exact k distance.

So, if the input is like k = 2

then the output will be 4

To solve this, we will follow these steps −

N := 5005

graph := adjacency list of size N

vertex_count := a 2d matrix of size 505 x 5005

res := 0

Define a function insert_edge() . This will take x, y

insert y at the end of graph[x]

insert x at the end of graph[y]

Define a function dfs() . This will take v, parent

vertex_count[v, 0] := 1

for each i in graph[v], do

if i is not same as parent, then

dfs(i, v)

for j in range 1 to k + 1, do

res := res + vertex_count[i, j - 1] * vertex_count[v, k - j]

for j in range 1 to k + 1, do

vertex_count[v, j] := vertex_count[v, j] + vertex_count[i, j - 1]

Let us see the following implementation to get better understanding −

N = 5005 graph = [[] for i in range(N)] vertex_count = [[0 for i in range(505)] for i in range(N)] res = 0 def insert_edge(x, y): graph[x].append(y) graph[y].append(x) def dfs(v, parent): global res vertex_count[v][0] = 1 for i in graph[v]: if (i != parent): dfs(i, v) for j in range(1, k + 1): res += vertex_count[i][j - 1] * vertex_count[v][k - j] for j in range(1, k + 1): vertex_count[v][j] += vertex_count[i][j - 1] k = 2 insert_edge(1, 2) insert_edge(2, 3) insert_edge(3, 4) insert_edge(2, 5) dfs(1, 0) print(res)

k = 2 insert_edge(1, 2) insert_edge(2, 3) insert_edge(3, 4) insert_edge(2, 5)

4

- Related Questions & Answers
- Count number of substrings with exactly k distinct characters in C++
- Maximize the number of sum pairs which are divisible by K in C++
- Find the number of distinct islands in a 2D matrix in Python
- Program to find length of longest substring which contains k distinct characters in Python
- Program to find number of sublists that contains exactly k different words in Python
- Find distance between two nodes of a Binary Tree in C++
- Find all distinct pairs with difference equal to k in Python
- Querying the number of distinct colors in a subtree of a colored tree using BIT in C++
- Program to find maximum value of k for which we can maintain safe distance in Python
- Find the cordinates of the fourth vertex of a rectangle with given 3 vertices in Python
- Find a permutation such that number of indices for which gcd(p[i], i) > 1 is exactly K in C++
- Python program to find tuples which have all elements divisible by K from a list of tuples
- Check whether given degrees of vertices represent a Graph or Tree in Python
- Find the minimum of maximum length of a jump required to reach the last island in exactly k jumps in Python
- Program to find number of distinct combinations that sum up to k in python

Advertisements