1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None
        self.parent = None

class BinaryTree():
    def __init__(self):
        self.root = None

cnt = 0

def solution(k, num, links):
    answer = 0
    tree = BinaryTree()
    node_list = []
    for i in range(len(num)):
        node_list.append(Node(num[i]))
    for i in range(len(links)):
        if links[i][0] != -1:
            node_list[i].left = node_list[links[i][0]]
            node_list[i].left.parent = node_list[i]
        if links[i][1] != -1:
            node_list[i].right = node_list[links[i][1]]
            node_list[i].right.parent = node_list[i]
    for i in range(len(num)):
        if node_list[i].parent == None:
            tree.root = node_list[i]
    left, right = 0, 10**9
    global cnt

    while left <= right:
        mid = (left + right) // 2
        cnt = 1
        a = dfs(tree.root, mid)
        if  cnt <= k:
            answer = mid
            right = mid -1
        else:
            left = mid + 1
    return answer

def dfs(cur, value):
    lv, rv = 0, 0
    global cnt
    if cur.left != None:
        lv = dfs(cur.left, value)
    if cur.right != None:
        rv = dfs(cur.right, value)
    if cur.item + lv + rv <= value:
        return cur.item + lv + rv
    if cur.item + min(lv, rv) <= value:
        cnt += 1
        return cur.item + min(lv, rv)
    if cur.item > value:
        cnt += 10**7
        return cur.item
    cnt += 2
    return cur.item