Longest Paths in Tree
Tag(s):

## Algorithms, Graph, 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

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Basic Math
• Data Structures > Advanced Data Structures