Edge Weight Assignment
Contest: Codeforces Round 633 (Div. 1)
Difficulty rating: 1800
Tags: bitmasks, constructive algorithms, dfs and similar, greedy, math, trees

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 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.

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$$$). 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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

In the second example, possible assignments for each minimum and maximum are described in picture below. The $$$f$$$ value of valid assignment of this tree is always $$$3$$$.

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

Example input:
6
1 3
2 3
3 4
4 5
5 6

Example output:
1 4

Example input:
6
1 3
2 3
3 4
4 5
4 6

Example output:
3 3

Editorial:
Let's make an easy and good construction which can solve actual problem. Now reroot this tree at any leaf like picture below;
Our goal in this construction is, we are trying to make $$$xor(path(l_{1}, lca(l_{1}, l_{2}))) = xor(path(l_{2}, lca(l_{1}, l_{2}))) = xor(path(root, lca(l_{1}, l_{2})))$$$ for all two leaves $$$l_{1}$$$ and $$$l_{2}$$$ to satisfy $$$xor(path(l_{1}, l_{2})) = 0$$$.
First, let's solve about minimum $$$f$$$ value.
Observation 1. You can prove that minimum value of $$$f$$$ is at most $$$3$$$, by following construction;
Weight of edges are only determined by degree of two vertices and whether that edge is connected to leaf or not. So answer for minimum value is at most $$$3$$$.
Observation 2. If there is any construction such that $$$f = 2$$$, then it is always possible to have construction of $$$f = 1$$$. Because if $$$f = 2$$$ then there should be even number of edges for each weight, and you can simply change all weights them to single value without violating validity of edge weight assignment.
If you want to check validity of $$$f = 1$$$ assignment, then you can simply check if all leaves have same parity of distance from root. Because distances between all nodes should be even.
Now let's solve about maximum value.
Observation 3. You can solve maximum value of $$$f$$$ by following construction;
So for each non-root vertex $$$i$$$, assign weight to edge between $$$i$$$ and $$$p_{i}$$$ by followings ($$$p_{i}$$$ is parent of vertex $$$i$$$);
• If $$$i$$$ is not leaf, then assign $$$2^{i}$$$ as weight.
• Otherwise, assign $$$xor(path(root, p_{i}))$$$ as weight.
This will differentize all edges' weights except for multiple leaves's edges which are connected to single vertex, because every non-leaf vertex have different weights of edge to its parent.
So the answer for maximum value is $$$e - l + m$$$, where
• $$$e$$$ is number of edges in this tree.
• $$$l$$$ is number of leaves in this tree.
• $$$m$$$ is number of non-leaves which has at least one leaf as its neighbor.
Time complexity is $$$O(n)$$$.
——————
(Update) There is an another way to approach, provided by Darooha.
If you label vertices instead of edges where all leaves have same label and none of neighbors have same label, then you can consider edge weight as xor of two vertices' labels, so this is basically equivalent to original problem.
Now for minimum, you can see that labelling $$$0$$$ to leaves, and $$$1, 2$$$ to non-leaves are enough, so you can prove minimum value of $$$f$$$ is at most $$$3$$$. In same manner, you can try parity checking to check if $$$f$$$ value can be $$$1$$$ or not.
For maximum, assign $$$0$$$ to all leaves and assign all different values($$$2^{1}, 2^{2}, \ldots$$$) to non-leaf vertices, then you can see all edge weights(except leaves connected to same vertex) are different.