4452: Directed Chain Decomposition
内存限制：128 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
There is a tree with n nodes (labeled 1, 2, …, n) and n − 1 directed edges. We can decompose the tree into several directed chains, and each edge appears in exactly one chain. Now you need to figure out the minimum number of edges that we need to reverse in order to minimize the minimum possible number of directed chains in the decomposition result.
For example, if we have a tree 1 → 2 → 3 ← 4, we can reverse the edge from node 4 to node 3, then the tree can be decomposed into only one directed chain.
输入格式
There will be at most 200 test cases. Each case begins with one integer n(3 ≤ n ≤ 105), the number of nodes. Each of the following n − 1 lines contains two integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi), denoting a directed edge from node ui to node vi. The size of the whole input file does not exceed 8MB.
输出格式
For each test case, print the minimum possible number of directed chains in the decomposition result, and the minimum number of edges that we need to reverse.
输入样例 复制
4
1 2
2 3
4 3
5
2 1
3 1
4 1
5 1
4
1 2
2 3
2 4输出样例 复制
1 1
2 2
2 0