Problem p02698 (python)

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
import bisect

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math
import bisect

def solve(seq):
    dp = [math.inf] * (len(seq) + 1)
    dp[0] = -1 * math.inf
    for value in seq:
        key = bisect.bisect_left(dp, value)
        dp[key] = value
        print('dp') # debug
        print(dp) # debug
    key = bisect.bisect_left(dp, math.inf)
    return key - 1

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math
from sortedcontainers import SortedList, SortedDict, SortedSet
import bisect

def solve(seq):
    dp = [math.inf] * (len(seq) + 1)
    dp[0] = -1 * math.inf
    for value in seq:
        key = bisect.bisect_left(dp, value)
        dp[key] = value
        print('dp') # debug
        print(dp) # debug
    key = bisect.bisect_left(dp, math.inf)
    return key - 1

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)



    print('\33[32m' + 'end' + '\033[0m') # debug

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.last_not_inf = 0
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        key, value = first_over_or_same(self.dp, math.inf)
        if key is None:
            return len(self.dp) - 1
        return key - 1


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.last_not_inf = 0
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        def from_end():
            length = len(self.dp) - 1
            while length >= 0:
                value = self.dp[length]
                if value is not math.inf and value > 0:
                    self.last_not_inf = length
                    return
                # for next
                length -= 1
            self.last_not_inf = 0
        if not (len(self.dp) > self.last_not_inf):
            from_end()
        if self.dp[self.last_not_inf] is math.inf:
            self.last_not_inf -= 1
        elif (len(self.dp) > self.last_not_inf + 1) and self.dp[self.last_not_inf + 1] is not math.inf:
            self.last_not_inf += 1
        return self.last_not_inf



class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        return -1
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append([])
        self.use(value, len(self.dp))
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        for d in self.history[-1]:
            self.dp[d.dp_key] = d.before_value

    def use(self, value, loop_end):
        for length, last_value in enumerate(self.dp[:loop_end + 1]):
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        if value < self.dp[length]:
            self.history[-1].append(SolverLIS.Diff(length, self.dp[length]))
            self.dp[length] = value



    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def iter_node_value(path, node_values):
    for node in path:
        yield node_values[node]

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef, path):
        path.append(node)
        # process
        value_list = list(iter_node_value(path, node_values))
        #print('value_list, node') # debug
        #print(value_list, node) # debug
        #ans[node] = longest_increment_size(value_list)
        ans[node] = solver.append_last(value_list[-1])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node, path)
        # exit recursive
        solver.remove_last()
        path.pop(-1)
    _dps(1, 0, [])
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')