思维！！、思维！！、树的遍历、递归

我是个渣滓。

题意：

没时间解释了，现在是时候拯救世界了。

你手上现在有一根古代神杖，它是一棵有n个顶点的无向树，你必须给树上的每条边都安排一个正权值来启动神杖。
其中正权值必须满足以下条件：对于任意两个不同的叶子节点v1，v2，v1到v2的简单路径上的权值异或（XOR）和必须为0。
注意，因为你是被选中的孩子，所以你有无限的魔力，你可以安排一个非常巨大的权值，例如10^10^10……
你可以认为，在给定的条件下，总是存在这样的安排。
定义F为一个安排中不同权值的个数。
图片说明
例如在这个例子中，这个安排是可行的，并且F的值为2.
而在这个例子中，这个安排是不可行的，因为从叶子顶点1到叶子顶点6的简单路径的异或和不为0。
图片说明
你认为，F的最小值与最大值对拯救世界是非常重要的参数，所以你希望知道他们。

Input
第一行包含一个整数n (3 ≤ n ≤ 100000) 代表树的顶点数。
接下来的n-1行每行包含两个数a,b 表示a顶点与b顶点存在一条无向边。

Output
输出两个数，f的最小值和f的最大值。

Examples
输入
6
1 3
2 3
3 4
4 5
5 6
输出
1 4

分析

这是个思维题
感觉思维题真是不好做，没有思路啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

让我们先来想一想，最少的情况！
首先显而易见的，如果各个叶子节点之间的距离都是偶数的话我们答案就是1，
我们让所有的边权值都为一个数就好了嘛。
需要思考的是当有的叶子节点之间的距离是奇数时我们该怎么办？
这个奇数 num一定是大于等于3的！！！注意n的范围
首先我们知道2是一定不行的！！！！（呜呜呜）
为什么呢假设我们选了两个a和b。那么对于任何一道路径必定是偶数个a奇数个b
或者偶数个b奇数个a。那么偶数的一方因为异或的性质一定会变为0，奇数的一方因为异或的性质一定会变为原来的数我们假设就为b吧。又因为b>0所以，0^b一定不为0！！！故两个不成立！
正确答案是3个！
1^2^3 = 0，看到了吗。就用1，2，3填，就行了！！！一定能填成。(呜呜呜呜呜~不着如何证明)

故，当有的叶子节点之间距离为奇数时，最小数目为3否则为1

下面来看看，如何确定最大值吧！！！！
首先我们知道如果两个叶子节点a,b他们的父节点是同一个的话，那么连接a,b的边的权值一定是相等的!
那么，我们就可以把这两个看成一个就好了。

那么答案就是，将子节点化为一后的边的个数。

我完全不会这种问题，，，，，，，唉唉唉，烦烦烦！！！