提示: 欢迎访问OurACM平台。
Problem 2185 树的路径覆盖

Accept: 120    Submit: 328
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

給一棵树, 用最少的路径去覆盖所有的边, 求(1)允许边被重复覆盖, (2)不允许边被重复覆盖.

Input

第一行是组数T(T <= 20). 每组两行, 第一行是n(1 <= n <= 10^5), 第二行是n - 1个数(0-based), 第i个数x[i]表示有一条边(x[i], i + 1), (0 <= i <= n - 2).

Output

两个值,第一个值是允许边被重复覆盖情况下的答案,第二个值是不允许边被重复覆盖下的答案,用一个空格分隔.

Sample Input

2 1 7 0 0 1 1 2 2

Sample Output

0 0 2 3

Source

FOJ有奖月赛-2015年03月

Submit  Back  Status  Discuss