Message Passing :
Difficulty Level : Medium
Submissions : 919
Asked In :
Marks :20
: 7 | : 1
You are in a corporate and you need to communicate about a strategic mission in-person to all the people in your company. This information can NOT be broadcasted so you have to tell it to each person in a $$$1-1$$$ session. It takes $$$1$$$ hour to communicate the information from one person to another. At any given point of time, a manager can communicate this vital strategic information to one of his/her direct reports. Let us say we have the following reporting structure: Find out the minimum number of hours in which the information can be communicated to all the members of the organization. Assuming that node $$$1$$$ has the information initially
The first line contains a single integer $$$1\le N \le 10^{5}$$$.
Following $$$N−1$$$ lines contains two space separated integers $$$u$$$ and $$$v$$$ which denotes $$$u$$$ and $$$v$$$ are connected by an edge
Output the minimum number of hours in which the information can be communicated to all the members of the organization if assuming that node $$$1$$$ has information initially.
17 1 2 1 3 1 4 1 5 1 6 1 7 2 8 2 9 2 10 8 11 8 12 5 13 5 14 13 15 14 16 7 17
6
In the given tree,
At the end of $$$1$$$ hour , $$$1$$$ will pass the info to $$$2$$$.
At the end of $$$2$$$ hour , $$$1$$$ will pass the info to $$$5$$$ , $$$2$$$ will pass the info to $$$8$$$.
At the end of $$$3$$$ hour , $$$1$$$ will pass the info to $$$7$$$ , $$$2$$$ will pass the info to $$$9$$$, $$$5$$$ will pass the info to $$$13$$$, $$$8$$$ will pass info to $$$11$$$.
... and so on.
Non circled numbers represent time to convey the information to respective nodes.
