Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
高橋君は、AtCoder 社のクリスマスパーティーに向けて、クリスマスツリーを作ることにしました。
クリスマスツリーとは 頂点に 1 から N まで番号付けられた N 頂点 N-1 辺の木で、 i(1\leq i\leq N-1) 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
高橋君は、以下の方法でクリスマスツリーを作りたいです。
- 2 つの非負整数 A,B を指定する。
- 長さ B 以下のクリスマスパスを A 個用意する。ただし、長さ X のクリスマスパスとは、X+1 頂点 X 辺からなるグラフであって、頂点に 1 から X+1 までの番号を適切につければ、i(1\leq i\leq X) 本目の辺が頂点 i と頂点 i+1 を結んでいるようにできるものを指す。
- 以下の操作を、全体が連結になるまで繰り返す。
- 異なる連結成分に属する 2 頂点 x,y をとる。頂点 x と頂点 y をまとめて 1 つの頂点にする。より正確には、頂点 y に接続するすべての辺 (p,y) について辺 (p,x) を追加したあと、頂点 y と、y に接続する辺をすべて削除する。
- 出来上がった木の各頂点に、適当な番号をつける。
高橋君は、クリスマスツリーを作ることのできるような組 (A,B) のうち、辞書順最小のものを求めたいです。 すなわち、A の最小値を求め、A の最小値を達成するという条件のもとで B の最小値も求めたいです。
高橋君にかわって、この問題を解いてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq a_i,b_i \leq N
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 : a_{N-1} b_{N-1}
出力
辞書順最小の (A,B) に対し、A,B を空白区切りで出力せよ。
入力例 1
7 1 2 2 3 2 4 4 5 4 6 6 7
出力例 1
3 2
下の図のような方法で、クリスマスツリーを作ることができます。
入力例 2
8 1 2 2 3 3 4 4 5 5 6 5 7 5 8
出力例 2
2 5
入力例 3
10 1 2 2 3 3 4 2 5 6 5 6 7 7 8 5 9 10 5
出力例 3
3 4
Score : 900 points
Problem Statement
Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.
A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.
He would like to make one as follows:
- Specify two non-negative integers A and B.
- Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
- Repeat the following operation until he has one connected tree:
- Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
- Properly number the vertices in the tree.
Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.
Solve this problem for him.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq a_i,b_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N a_1 b_1 : a_{N-1} b_{N-1}
Output
For the lexicographically smallest (A,B), print A and B with a space in between.
Sample Input 1
7 1 2 2 3 2 4 4 5 4 6 6 7
Sample Output 1
3 2
We can make a Christmas Tree as shown in the figure below:
Sample Input 2
8 1 2 2 3 3 4 4 5 5 6 5 7 5 8
Sample Output 2
2 5
Sample Input 3
10 1 2 2 3 3 4 2 5 6 5 6 7 7 8 5 9 10 5
Sample Output 3
3 4