Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:

We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.



Sample input:
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10


Sample output:
1
2
3
3
4
4
5
2
2
3

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def make_order(g, v):
    seen = [False]*g.N
    pre_order = [-1]*g.N
    post_order = [-1]*g.N
    counters = {"pre": 0, "post": 0}

    parent = [-1]*g.N

    def recur(v):
        pre_order[counters["pre"]] = v
        counters["pre"] += 1

        seen[v] = True
        for to, w in g.E[v]:
            if seen[to] == True:
                continue
            parent[to] = v
            recur(to)

        post_order[counters["post"]] = v
        counters["post"] += 1

    recur(v)
    return pre_order, post_order


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    pre_order, post_order = make_order(g, 0)
    # print(pre_order, post_order, parent, sep="\n")
    post_order += [-1]
    post = 0
    seen = [False]*(N+10)
    # return

    for i, curr in enumerate(pre_order):
        # print(i, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])
        seen[curr] = True

        while seen[post_order[post]]:
            if len(event) > 0:
                c, i, v = event.pop()
                dp[i] = v
                post += 1

    print(*ans, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    def dfs(curr, par):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr)

        c, i, v = event[-1]
        if c == curr:
            dp[i] = v
            event.pop()

    dfs(0, -1)
    print(*ans, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def LIS(seq):
    DP = [INF]
    for i in seq:
        if DP[-1] < i:
            DP.append(i)
        else:
            DP[bisect_left(DP, i)] = i
    return len(DP)


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    def dfs(curr, par, dp):
        # 親からdpテーブルを貰う
        if dp[-1] < a[curr]:
            dp.append(a[curr])
        else:
            dp[bisect_left(dp, a[curr])] = a[curr]
        ans[curr] = len(dp)

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr, dp[:])

    dfs(0, -1, [INF])
    print(*ans, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)

    def euler_tour(self):
        res = []
        begin = [None for _ in range(self.n)]
        end = [None for _ in range(self.n)]
        visited = [0 for _ in range(self.n)]
        visited[self.root] = 1
        stack = [self.root]
        while stack:
            node = stack.pop()
            res.append(node)
            end[node] = len(res)
            if begin[node] is None:
                begin[node] = len(res) - 1
            for adj in self.tree[node]:
                if visited[adj]:
                    continue
                visited[adj] = 1
                stack.append(node)
                stack.append(adj)
        return res, begin, end

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
T.setroot(0)
et, _, _ = T.euler_tour()

res = [None for _ in range(N)]
lis = []
rec = [None for _ in range(N)]
prev = None

for node in et:
    if res[node] is None:
        if not lis or A[node] > lis[-1]:
            lis.append(A[node])
        else:
            idx = bisect_left(lis, A[node])
            rec[node] = (idx, lis[idx])
            lis[idx] = A[node]

        res[node] = len(lis)
    else:
        if rec[prev] is not None:
            lis[rec[prev][0]] = rec[prev][1]
        else:
            lis.pop()
    prev = node

print('\n'.join(map(str, res)))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c
 
sys.setrecursionlimit(10 ** 6)
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[] for i in range(n)]
 
for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    elif parent[l[0]-1]==float('inf'):
        parent[l[0]-1]=l[1]-1
    else:
        setParent(l[1]-1,parent)
        parent[l[1]-1]=l[0]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    root[i].append(a[i])
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break
 
print(1)
for i in range(1,n):
    root[i].extend([a[0]])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c

sys.setrecursionlimit(10 ** 6)
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[] for i in range(n)]
 
for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    elif parent[l[0]-1]==float('inf'):
        parent[l[0]-1]=l[1]-1
    else:
        setParent(l[1]-1,parent)
        parent[l[1]-1]=l[0]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    root[i].append(a[i])
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break
 
print(1)
for i in range(1,n):
    root[i].extend([a[0]])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf')  for i in range(n) ]

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = {}
dp = [ float('inf')  for i in range(n) ]

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = [ [] for _ in range(n) ]

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = [ set() for i in range(n) ]

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].add(v - 1)
    nbs[v - 1].add(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    oidx = 0
    ov = 0
    
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = a[cur]
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)
    dp[idx] = ov



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, a[cur])
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = a[cur]
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)
    dp[idx] = ov



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



mlen[0] = 1
dp[0] = a[0]
for ch in nbs[0]:
    getmlen(ch, 0, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



mlen[0] = 1
dp[0] = a[0]
for ch in nbs[0]:
    getmlen(ch, 0, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


n = int(input())
a = tuple(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))



n = int(input())
a = tuple(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, dp, nbs, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, dp, nbs, ntail)

    dp[idx] = ov
    return


n = int(input())
a = tuple(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, dp, nbs, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import sys
import resource
import bisect

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, dp, nbs, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, dp, nbs, ntail)

    dp[idx] = ov
    return


n = int(input())
a = tuple(map(int, input().split()))

nbs = [ [] for i in range(n) ]

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, dp, nbs, 0)

for i in range(n):
    print(mlen[i])

Submission status: Time Limit Exceeded

Solution code:
#!/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

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)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if e[-1] < c:
            dp[i] = e.copy()+[c]
            ans[i] = x+1
        else:
            dp[i] = e.copy()
            ans[i] = x
        d = dp[i]
        for j in range(x-1,-1,-1):
            if j == 0 and d[j] > c:
                d[j] = c
            elif d[j] > c and d[j-1] < c:
                d[j] = c
                
for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N)]
for u, v in uv:
    link[u - 1].append(v - 1)
    link[v - 1].append(u - 1)


def dfs(l, visit, v, dp):
    visit[v] = True
    # LIS
    if dp[-1] < A[v]:
        dp = np.append(dp, A[v])
    else:
        i = np.searchsorted(dp, A[v])
        dp[i] = A[v]
    l[v] = len(dp)

    for x in link[v]:
        if not visit[x]:
            dfs(l, visit, x, dp.copy())


def main():
    visit = [False] * N
    l = [None] * N
    dfs(l, visit, 0, np.array([A[0]]))
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]


def dfs(l, visit, link, v, dp):
    visit[v] = True
    # LIS
    if dp[-1] < A[v]:
        dp = np.append(dp, A[v])
    else:
        i = np.searchsorted(dp, A[v])
        dp[i] = A[v]
    l[v] = len(dp)

    for x in link[v]:
        if not visit[x]:
            dfs(l, visit, link, x, dp.copy())


def main():
    link = [[] for _ in range(N)]
    for u, v in uv:
        link[u - 1].append(v - 1)
        link[v - 1].append(u - 1)
    
    visit = [False] * N
    l = [None] * N
    dfs(l, visit, link, 0, np.array([A[0]]))
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]
    dp2 = [0] * (N+1)
    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
            dp2[node] = 1
        else:
            dp2[node] = dp2[parent]
            a = A[node]
            done = False
            for i, val in enumerate(dp[parent][1:], 1):
                if val > a and not done:
                    if val == float('inf'):
                        dp2[node] += 1
                    dp[node].append(a)
                    done = True
                else:
                    dp[node].append(val)
            if dp[node][-1] < a:
                dp[node].append(a)
                dp2[node] += 1
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

    for i in range(1, N+1):
        print(dp2[i])


if __name__ == "__main__":
    run()