Problem:


Score : 1400 points

Problem Statement

We will recursively define uninity of a tree, as follows: (Uni is a Japanese word for sea urchins.)

A tree consisting of one vertex is a tree of uninity 0.

Suppose there are zero or more trees of uninity k, and a vertex v. If a vertex is selected from each tree of uninity k and connected to v with an edge, the resulting tree is a tree of uninity k+1.

It can be shown that a tree of uninity k is also a tree of uninity k+1,k+2,..., and so forth.

You are given a tree consisting of N vertices.
The vertices of the tree are numbered 1 through N, and the i-th of the N-1 edges connects vertices a_i and b_i.

Find the minimum k such that the given tree is a tree of uninity k.

Constraints

2 ≦ N ≦ 10^5

1 ≦ a_i, b_i ≦ N(1 ≦ i ≦ N-1)

The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

Print the minimum k such that the given tree is a tree of uninity k.

Sample Input 1

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

Sample Output 1

2

A tree of uninity 1 consisting of vertices 1, 2, 3 and 4 can be constructed from the following: a tree of uninity 0 consisting of vertex 1, a tree of uninity 0 consisting of vertex 3, a tree of uninity 0 consisting of vertex 4, and vertex 2.

A tree of uninity 1 consisting of vertices 5 and 7 can be constructed from the following: a tree of uninity 1 consisting of vertex 5, and vertex 7.

A tree of uninity 2 consisting of vertices 1, 2, 3, 4, 5, 6 and 7 can be constructed from the following: a tree of uninity 1 consisting of vertex 1, 2, 3 and 4, a tree of uninity 1 consisting of vertex 5 and 7, and vertex 6.

Sample Input 2

12
1 2
2 3
2 4
4 5
5 6
6 7
7 8
5 9
9 10
10 11
11 12

Sample Output 2

3



Sample input:
7
1 2
2 3
2 4
4 6
6 7
7 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

graph

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

uninity = [0] * (N+1)
dp = [(1<<60)-1] * (N+1) # 使用可能なbitの集合
for x in order[::-1]:
    p = parent[x]
    # 使用可能なmin
    lsb = dp[x] & (-dp[x])
    uninity[x] = lsb
    dp[x] ^= lsb
    dp[x] |= (lsb - 1)
    dp[p] &= dp[x]

x = max(uninity).bit_length() - 1
print(x)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def calc(rt):
    e = edge[rt]
    f[rt] = 1
    g[rt] = 1
    g1 = 0
    g2 = 0
    for son in e:
        if(f[son] == 0):
            calc(son)
            res = f[son]
            if(res > f[rt]):
                f[rt] = res
            res = g[son]
            if res + 1 > g[rt]:
                g[rt] = res + 1
            if(res > g1):
                g2 = g1
                g1 = res
            elif (res > g2):
                g2 = res
    if g1 + g2 + 1 > f[rt]:
        f[rt] = g1 + g2 + 1
    if g[rt] > f[rt]:
        f[rt] = g[rt]

n = int(input())
edge = []
f = []
g = []
for i in range(0,n):
    edge.append(set())
    f.append(0)
    g.append(0)

for i in range(1,n):
    e = input().split(' ')
    y = int(e[0]) - 1
    x = int(e[1]) - 1
    edge[x].add(y)
    edge[y].add(x)

calc(0)

length = f[0]
ans = 0
l = 1
while l < length:
    ans = ans + 1
    l = l + l + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

uninity = [0] * (N+1)
dp = [np.zeros(30,np.int64) for _ in range(N+1)]
answer = -1
for x in order[::-1]:
    p = parent[x]
    A = dp[x]
    twice = (A >= 2)
    if np.any(twice):
        k = np.where(twice)[0].max()
        A[:k] = 1
    lsb = np.where(A == 0)[0].min()
    if answer < lsb:
        answer += 1
    uninity[x] = lsb
    A[lsb] = 1
    A[:lsb] = 0
    A[A>0] = 1
    dp[p] += A

print(answer)

Submission status: Accepted

Solution code:
import sys
range = xrange

def decomp(coupl, root = 0):
    n = len(coupl)
    visible_labels = [0] * n
    
    bfs = [root]
    for node in bfs:
        for nei in coupl[node]:
            coupl[nei].remove(node)
        bfs += coupl[node]

    for node in reversed(bfs):
        seen = seen_twice = 0
        for nei in coupl[node]:
            seen_twice |= seen & visible_labels[nei]
            seen |= visible_labels[nei]
        tmp = ~seen & -(1 << seen_twice.bit_length()) 
        label = tmp & -tmp
        visible_labels[node] = (label | seen) & -label
    
    return [(seen & -seen).bit_length() - 1 for seen in visible_labels]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0

n = inp[ii]; ii += 1
coupl = [[] for _ in range(n)]
for _ in range(n - 1):
    u = inp[ii] - 1; ii += 1
    v = inp[ii] - 1; ii += 1
    coupl[u].append(v)
    coupl[v].append(u)

print max(decomp(coupl))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

full = (1 << 60) - 1
uninity = [0] * (N+1)
dp = [0] * (N+1)
twice = [0] * (N+1)
for x in order[::-1]:
    p = parent[x]
    n = twice[x].bit_length() - 1
    if n >= 0:
        dp[x] |= (1 << (n+1)) - 1
    can_use = full & (~dp[x])
    lsb = can_use & (-can_use)
    uninity[x] = lsb
    dp[x] |= lsb
    dp[x] &= full & ~(lsb - 1)
    
    twice[p] |= (dp[x] & dp[p])
    dp[p] |= dp[x]

x = max(uninity)
answer = x.bit_length() - 1
print(answer)