307318: CF1338B. Edge Weight Assignment
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Edge Weight Assignment
题意翻译
### 题目描述 给定一棵 $n$ 个点的无根树,要求给每条边分配一个**正整数**权值,使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值,以及最多可以使用多少种不同权值。 这里,填入的边权值可以为任意大。 ### 数据范围 $3 \le n\le 10^5$题目描述
You have unweighted tree of $ n $ vertices. You have to assign a positive weight to each edge so that the following condition would hold: - For every two different leaves $ v_{1} $ and $ v_{2} $ of this tree, [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of all edges on the simple path between $ v_{1} $ and $ v_{2} $ has to be equal to $ 0 $ . Note that you can put very large positive integers (like $ 10^{(10^{10})} $ ). It's guaranteed that such assignment always exists under given constraints. Now let's define $ f $ as the number of distinct weights in assignment. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1338B/eb47baeab358a9bf4d6536421055c2c258904b33.png) In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is $ 0 $ . $ f $ value is $ 2 $ here, because there are $ 2 $ distinct edge weights( $ 4 $ and $ 5 $ ).![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1338B/158a70d1382d5b7e8863700d0f77901af19c305f.png) In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex $ 1 $ and vertex $ 6 $ ( $ 3, 4, 5, 4 $ ) is not $ 0 $ . What are the minimum and the maximum possible values of $ f $ for the given tree? Find and print both.输入输出格式
输入格式
The first line contains integer $ n $ ( $ 3 \le n \le 10^{5} $ ) — the number of vertices in given tree. The $ i $ -th of the next $ n-1 $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1 \le a_{i} \lt b_{i} \le n $ ) — it means there is an edge between $ a_{i} $ and $ b_{i} $ . It is guaranteed that given graph forms tree of $ n $ vertices.
输出格式
Print two integers — the minimum and maximum possible value of $ f $ can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.
输入输出样例
输入样例 #1
6
1 3
2 3
3 4
4 5
5 6
输出样例 #1
1 4
输入样例 #2
6
1 3
2 3
3 4
4 5
4 6
输出样例 #2
3 3
输入样例 #3
7
1 2
2 7
3 4
4 7
5 6
6 7
输出样例 #3
1 6