Edge Weight Assignment (Codeforces 1339D)
Tags: Greedy, bitmasks

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

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.   

Sample Inputs:
6
1 3
2 3
3 4
4 5
5 6

6
1 3
2 3
3 4
4 5
4 6

7
1 2
2 7
3 4
4 7
5 6
6 7

Sample Outputs:
1 4

3 3

1 6

Solution (Python):
import sys
(n, *ab) = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for (a, b) in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    rank = [None] * n
    rank[0] = 0
    parent = [None] * n
    leaves = []
    stack = [0]
    while stack:
        u = stack.pop()
        if not u == 0 and len(graph[u]) == 1:
            leaves.append(u)
            continue
        for v in graph[u]:
            if v == parent[u]:
                continue
            parent[v] = u
            rank[v] = rank[u] + 1
            stack.append(v)
    if len(graph[0]) == 1:
        leaves.append(0)
        parent[0] = graph[0][0]
        parent[graph[0][0]] = None
    pars = set()
    for leaf in leaves:
        pars.add(parent[leaf])
    ma = n - 1 - (len(leaves) - len(pars))
    rs = set([rank[leaf] & 1 for leaf in leaves])
    mi = 1 if len(rs) == 1 else 3
    print(mi, ma)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.readline())

def MI():
    return map(int, sys.stdin.readline().split())

def MI1():
    return map(int1, sys.stdin.readline().split())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def SI():
    return sys.stdin.readline()[:-1]

def main():

    def findmin():
        p = dep[leaf[0]] & 1
        for u in leaf[1:]:
            if dep[u] & 1 != p:
                return 3
        return 1
    n = II()
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = MI1()
        to[u].append(v)
        to[v].append(u)
    dep = [-1] * n
    dep[0] = 0
    pp = [-1] * n
    stack = [0]
    while stack:
        u = stack.pop()
        for v in to[u]:
            if v == pp[u]:
                continue
            pp[v] = u
            dep[v] = dep[u] + 1
            stack.append(v)
    leaf = []
    for u in range(n):
        if len(to[u]) == 1:
            leaf.append(u)
    mn = findmin()
    st = set()
    cnt = 0
    for u in leaf:
        p = to[u][0]
        if p in st:
            cnt += 1
        else:
            st.add(p)
    mx = n - 1 - cnt
    print(mn, mx)
main()

Solution (Python):
import sys
import collections
import threading

def main():
    input = sys.stdin.readline
    n = int(input())
    d = collections.defaultdict(list)
    try:
        for i in range(1, n):
            (a, b) = map(int, input().split())
            d[a].append(b)
            d[b].append(a)
        parents = set()
        cnt = 0
        for key in d:
            if len(d[key]) == 1:
                cnt += 1
                parents.add(*d[key])
                leave = key

        def dfsmin(par, node, h, result):
            for i in d[node]:
                if i != par:
                    dfsmin(node, i, h + 1, result)
            if len(d[node]) == 1:
                result[h % 2] += 1
            return result
        minans = 1
        if dfsmin(-1, leave, 0, [0, 0])[1] > 0:
            minans = 3
        maxans = n - 1 - cnt + len(parents)
        print(minans, maxans)
    except RuntimeError as e:
        print(e)
sys.setrecursionlimit(2097152)
threading.stack_size(134217728)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()