### PROBLEM LINK:

**Author:** Abhijeet Jha

**Tester:** Teja Vardhan Reddy

**Editorialist:** Aswin Ashok

### DIFFICULTY:

EASY

### PREREQUISITES:

### PROBLEM:

A tree containing **N nodes and rooted at node 1 is given**. On each node of the tree, there is a monkey having information about a **graph G**.

G is a graph containing N nodes. The information contained on each node is an edge of the graph G .

**Now for every node X, consider the path from root to X**. You have to collect the information about edges from this path and construct a new **graph G’**. The constructed graph G’ will be a sub-graph of graph G obviously.

**For each node you need to find the number of connected component in graph G’.**

### EXPLANATION:

Given a tree with N nodes rooted at 1. Each of the tree nodes contain

an edge of a Graph G with also has N nodes. Each path in the tree gives some of

the edges of the graph G and the graph formed by this is a sub-graph of G and let us

call it G’. **We are asked to find number of connected components in G’ (s) formed
by all the paths from 1 to i (where i=1 to N).**

### SOLUTION:

Let us initialize the number of connected components in **G’ as N**, let’s call it **cc**. We

can do a **DFS** from the **node 1** of the tree. As and when we reach a node **i** we can

check if the edge contained in the node connects two disjoint components in **G’**

using Union Disjoint Find. If yes we can * reduce cc and store the answer for path 1**

to i in answer and store the roots of nodes in the edge and do union operation.

When the **DFS retraces back** we can use the stored to roots to see if the union

operation at that particular node reduced cc. **If yes we can undo the union
operation.**

Once the DFS completes get we the required answers.

### TIME COMPLEXITY

Using Union Disjoint Find we can find the roots in O(logN) and do

union or undo it in O(1). There are N nodes in the tree so Overall time complexity

is O(NlogN).

### SOLUTIONS LINKS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.