All Tracks Algorithms Graphs Depth First Search Problem

Longest Paths in Tree
Tag(s):

Algorithms, Medium

Problem
Editorial
Analytics

You are given a tree. Simple path of length $$m$$ is a sequence of vertices $$v_1, v_2, \dots, v_m$$ such that

  • All $$v_i$$ are distinct.
  • $$v_i$$ and $$v_{i+1}$$ are connected by edge for $$1 \leqslant i \leqslant m - 1$$.

For each vertex find length of longest simple path that goes through this vertex. Also count number of this paths. Two paths considered distinct if set of vertices of this paths differ.

Input Format:
First line of input contains single positive integer $$n$$ -- number of vertices of the tree.
Next $$n - 1$$ lines contains pairs space-separated integers $$u_i, v_i$$ -- edges of the tree.

Output Format:
Output $$n$$ lines. $$i$$-th line must contain two integers -- length of the longest simple path containing vertex $$i$$ and number of such paths.

Constraints:
$$1 \leqslant n \leqslant 300,000.$$

Scoring:
50 points
Additionally $$n \leqslant 3,000$$.
50 points
No additional constraints.

SAMPLE INPUT
4
1 2
3 2
4 2
SAMPLE OUTPUT
3 2
3 3
3 2
3 2
Explanation

Longest paths going through vertex $$1$$: $$(1, 2, 3)$$, $$(1, 2, 4)$$.
Longest paths going through vertex $$2$$: $$(1, 2, 3)$$, $$(1, 2, 4)$$, $$(3, 2, 4)$$.
Cases of vertices $$3$$ and $$4$$ are similar to vertex $$1$$.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications