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: Wrong Answer

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def rewind():
        while stack:
            cur, index, pv = stack.pop()
            if cur == -1:
                break
            ans[cur] = bisect.bisect_left(dp, INF)
            dp[index] = pv

    n = int(input())
    a = list(map(int, readline().split()))
    node = {i: [] for i in range(n)}

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

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]

    from collections import deque
    import bisect

    dfs = deque()
    stack = deque()
    dfs.append(0)

    while dfs:
        cur = dfs.pop()
        nv = a[cur]
        index = bisect.bisect_left(dp, nv)
        pv = dp[index]
        dp[index] = nv
        stack.append((cur, index, pv))
        suc = node[cur]
        if suc:
            if len(suc) >= 2:
                for i, nx in enumerate(suc):
                    dfs.append(nx)
                    if i != 0:
                        stack.append((-1, -1, -1))
            else:
                dfs.append(suc[0])
        else:
            rewind()

    while stack:
        cur, index, pv = stack.pop()
        if cur == -1:
            continue
        ans[cur] = bisect.bisect_left(dp, INF)
        dp[index] = pv

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def rewind():
        while stack:
            cur, index, pv = stack.pop()
            if cur == -1:
                break
            ans[cur] = bisect.bisect_left(dp, INF)
            dp[index] = pv

    n = int(input())
    a = list(map(int, readline().split()))
    node = {i: [] for i in range(n)}

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

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]

    from collections import deque
    import bisect

    dfs = deque()
    stack = deque()
    dfs.append(0)

    while dfs:
        cur = dfs.pop()
        nv = a[cur]
        index = bisect.bisect_left(dp, nv)
        pv = dp[index]
        dp[index] = nv
        stack.append((cur, index, pv))
        suc = node[cur]
        if suc:
            if len(suc) >= 2:
                for i, nx in enumerate(suc):
                    dfs.append(nx)
                    if i != 0:
                        stack.append((-1, -1, -1))
            else:
                dfs.append(suc[0])
        else:
            rewind()

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(3*10**5)

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = sorted(map(int,input().split()))
    u -= 1
    v -= 1
    T[u].add(v)

A = [INF]*N

ans = [0]*N

def dfs(V):
    num = a[V]
    k = bisect.bisect_left(A,num)
    v = A[k]
    A[k] = num
    ans[V] = bisect.bisect_left(A,INF)
    # このにぶたん無駄じゃね？まあ間に合うからいいか……
    for VV in T[V]:
        dfs(VV)
    A[k] = v

dfs(0)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = sorted(map(int,input().split()))
    u -= 1
    v -= 1
    T[u].add(v)

A = list()

ans = [1]*N

D = deque()

def head(V):
    num = a[V]
    k = INF
    y = INF
    if V == 0 or num > A[-1]:
        A.append(num)
    else:
        k = bisect.bisect_left(A,num)
        y = A[k]
        A[k] = num
    ans[V] = len(A)
    D.append((tail,k,y))
    for VV in T[V]:
        D.append((head,VV))

def tail(k,y):
    if y == INF:
        A.pop()
    else:
        A[k] = y

D.append((head,0))

while len(D) != 0:
    elemD = D.pop()
    elemD[0](*elemD[1:])

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = sorted(map(int,input().split()))
    u -= 1
    v -= 1
    T[u].add(v)

A = list()

ans = [1]*N

D = deque()

def head(V):
    num = a[V]
    k = INF
    y = INF
    if V == 0 or num > A[-1]:
        A.append(num)
    else:
        k = bisect.bisect_left(A,num)
        y = A[k]
        A[k] = num
    ans[V] = len(A)
    D.append((tail,k,y))
    for VV in T[V]:
        D.append((head,VV))

def tail(k,y):
    if y == INF:
        A.pop()
    else:
        A[k] = y

D.append((head,0))

while len(D) != 0:
    elemD = D.pop()
    elemD[0](*elemD[1:])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append((changeID, LIS[changeID]))
    LIS[changeID] = min(A[i], LIS[changeID])
    #print(i, LIS)
    #print(changed)
    Ans[i] = bisect_left(LIS, INF) + 1
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backID, backV = changed.pop()
    LIS[backID] = backV
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append((changeID, LIS[changeID]))
    LIS[changeID] = min(A[i], LIS[changeID])
    #print(i, LIS)
    print(changed)
    Ans[i] = bisect_left(LIS, N + 1)
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backID, backV = changed.pop()
    LIS[backID] = backV
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append(LIS[changeID])
    LIS[changeID] = min(A[i], LIS[changeID])
    Ans[i] = bisect_left(LIS, A[i] + 1)
    #print(i, Ans, LIS)
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    LIS[changeID] = changed.pop()
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * (N + 1)

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append(LIS[changeID])
    LIS[changeID] = min(A[i], LIS[changeID])
    Ans[i] = changeID + 1
    #print(i, Ans, LIS)
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backNum = changed.pop()
    LIS[changeID] = backNum
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [10 ** 20] * (N + 1)

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append(LIS[changeID])
    LIS[changeID] = A[i]
    Ans[i] = changeID + 1
    #print(i, Ans, LIS)
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backNum = changed.pop()
    LIS[changeID] = backNum
    return 0


def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import defaultdict as dd
N = int(input())
As = list(map(int, input().split()))
Es = dd(dict)
for _ in range(N-1):
    f, t = map(int, input().split())
    Es[f-1][t-1] = Es[t-1][f-1] = 1

INF = float('inf')
RET = 0
PROC = 1

stack = []
lismin = [INF] * N
anss = [INF] * N
visited = [False] * N

stack.append((RET, 0, INF))
stack.append((PROC, 0, 0))
while stack:
    cmd, *v = stack.pop()
    if cmd == RET:
        i, backup = v
        lismin[i] = backup
    else:
        node, i = v
        lismin[i] = As[node]
        anss[node] = i+1
        visited[node] = True
        for to in Es[node].keys():
            if not visited[to]:
                x = bisect_left(lismin, As[to])
                stack.append((RET, x, lismin[x]))
                stack.append((PROC, to, x))
for ans in anss:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    if len(seq)<= pos:
        seq.append(a[i-1])
        added  = 1
    else:
        old = seq[pos]
        seq[pos]=a[i-1]
    ans[i-1]=len(seq)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    if added==1:
        seq=seq[:-1]
    else:
        seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = []
ans = [-1]*(N)

dfs(1,-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def dfs(graph, root, A, res, lis):
    stack = [(root,)]
    while stack:
        # print(stack)
        state = stack[-1]
        del stack[-1]
        u = state[0]
        if res[u] == -1:
            a = A[u]
            p = bisect.bisect_left(lis, a)
            res[u] = p
            if p == len(lis):
                stack.append((u, 0))
                lis.append(a)
            else:
                stack.append((u, lis[p]))
                lis[p] = a
            for v in graph[u]:
                if res[v] == -1:
                    stack.append((v,))
        else:
            val = state[1]
            if val:
                lis[res[u]] = val
            else:
                del lis[-1]

n = int(input())
A = [int(x) for x in input().split()]
graph = [[] for i in range(n)]
for i in range(n - 1):
    u, v = [int(x) - 1 for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)
res = [-1] * n
dfs(graph, 0, A, res, [0])
print(*res, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
from  bisect import bisect_left
input = sys.stdin.readline
INF = 1 << 30

MAXN = 200005
G = [[] for _ in range(MAXN)]
dp = [INF] * MAXN
stack = []
ans = [None] * MAXN
def dfs(v,A,p = -1):
    idx = bisect_left(dp,A[v])
    stack.append((idx,dp[idx]))
    dp[idx] = A[v]
    ans[v] = idx + 1
    for e in G[v]:
        if e == p:
            continue
        dfs(e,A,v)
    idx,p = stack.pop()
    dp[idx] = p

def main():
    N = int(input())
    A = list(map(int,input().split()))
    for _ in range(N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    dfs(0,A)
    print('\n'.join(map(str,ans[:N])))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

N = int(input())
A = list(map(int,input().split()))
G = [[] for _ in range(N)]

for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

B = sorted(list(set(A)))
toID = {i:j for i,j  in zip(B,range(1,len(B) + 1))}
dp = SegmentTree([0] * (len(B) + 1))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] < a:
        ans[v] = a
        dp.update(idx,a)
        flag = True
    else:
        ans[v] = before[v]
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

N = int(input())
A = list(map(int,input().split()))
G = [[] for _ in range(N)]

for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

B = sorted(list(set(A)))
toID = {i:j for i,j  in zip(B,range(len(B)))}
dp = SegmentTree([0] * len(B))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] <= a:
        ans[v] = a
        dp.update(idx,a)
        flag = True
    else:
        ans[v] = before[v]
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

N = int(input())
A = list(map(int,input().split()))
G = [[] for _ in range(N)]

for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

B = sorted(list(set(A)))
toID = {i:j for i,j  in zip(B,range(len(B)))}
dp = SegmentTree([0] * len(B))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] < a:
        ans[v] = a
        dp.update(idx,a)
        flag = True
    else:
        ans[v] = before[v]
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
from bisect import bisect_left

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)

N = int(input())
A = list(map(int,input().split()))
G = [[] for _ in range(N)]

for _ in range(N - 1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

B = sorted(A)
dp = SegmentTree([0] * len(B))
ans = [0] * N
before = [0] * len(B)

def dfs(v,p = -1):
    idx = bisect_left(B,A[v])
    ans[v] = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    dp.update(idx,ans[v])
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    dp.update(idx,before[v])
    
dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
def main():

    from bisect import bisect_left as bl

    n = int(input())
    a = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    visited = [False]*n

    q = [-1, 0]
    lis = []
    while len(q) > 1:
        i = q.pop()
        ai = a[i]
        if not visited[i]:
            b = bl(lis, ai)
            if b == len(lis):
                visited[i] = "push"
                lis.append(ai)
            else:
                visited[i] = [b, lis[b]]
                lis[b] = ai
            print(len(lis))
        if not g[i]:
            if visited[i] == "push":
                lis.pop()
            else:
                lis[visited[i][0]] = visited[i][1]
        else:
            q.append(i)
            j = g[i].pop()
            g[j].remove(i)
            q.append(j)


main()

Submission status: Wrong Answer

Solution code:
def main():

    from bisect import bisect_left as bl

    n = int(input())
    a = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    visited = [False]*n

    q = [-1, 0]
    lis = []
    while len(q) > 1:
        i = q.pop()
        ai = a[i]
        if not visited[i]:
            b = bl(lis, ai)
            if b == len(lis):
                visited[i] = "push"
                lis.append(ai)
            else:
                visited[i] = [b, lis[b]]
                lis[b] = ai
            print(len(lis))
        if not g[i]:
            if visited[i] == "push":
                lis.pop()
            else:
                lis[visited[i][0]] = visited[i][1]
        else:
            q.append(i)
            j = g[i].pop()
            g[j].remove(i)
            q.append(j)


main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
Edge=[[] for _ in range(N)]
loute=[str(0)]*N
for i in range(N-1):
    u,v=map(int,input().split())
    if u>v:
        u,v=v,u
    Edge[u-1].append(v-1)
  
tmp=deque(str(0))
CHN=deque()
LIS=[10**18]*N
label=[False]*N
while tmp:
    T0=int(tmp[-1])
    if label[T0]:
        tmp.pop()
        pos,Val=CHN.pop()
        LIS[pos]=Val
        continue

    pos=bisect.bisect_left(LIS,A[T0])
    CHN.append((pos,LIS[pos]))
    LIS[pos]=A[T0]
    ans[T0]=bisect.bisect_left(LIS,10**18)

    if Edge[T0]:
        for i in Edge[T0]:
            tmp.append(i)
        label[T0]=True
    else:
        label[T0]=True
    
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
Edge=[[] for _ in range(N)]
loute=[str(0)]*N
for i in range(N-1):
    u,v=map(int,input().split())
    Edge[u-1].append(v-1)
  
tmp=deque(str(0))
CHN=deque()
LIS=[10**18]*N
label=[False]*N
while tmp:
    T0=int(tmp[-1])
    if label[T0]:
        tmp.pop()
        pos,Val=CHN.pop()
        LIS[pos]=Val
        continue

    pos=bisect.bisect_left(LIS,A[T0])
    CHN.append((pos,LIS[pos]))
    LIS[pos]=A[T0]
    ans[T0]=bisect.bisect_left(LIS,10**18)

    if Edge[T0]:
        for i in Edge[T0]:
            tmp.append(i)
        label[T0]=True
    else:
        label[T0]=True
    
for i in range(N):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
A = list(map(int,input().split()))
UV = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v)
    es[v].append(u)

from bisect import bisect
lis = [A[0]]
stack = []
ans = [1] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        i = bisect(lis, A[to])
        if i == len(lis):
            stack.append((i,-1))
            lis.append(A[to])
        else:
            stack.append((i,lis[i]))
            lis[i] = A[to]
        ans[to] = len(lis)

        dfs(to,v)

        i,a = stack.pop()
        if a < 0:
            lis.pop()
        else:
            lis[i] = a

dfs(0)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
import bisect
sys.setrecursionlimit(10**6)

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

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

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    for child in rooted[node]:
        dfs(child)
    table[p] = old
    lis[node] = p + 1

dfs(0)
print(*map(str, lis), sep="\n")

Submission status: Wrong Answer

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


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

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


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 = [None]*N
    var = {"e": 0, "last": 0}

    def dfs(curr):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                var["last"] = i
            event[var["e"]] = (curr, i, dp[i])
            dp[i] = a[curr]
            var["e"] += 1

        ans[curr] = len(dp[:var["last"]+1])

        for child in g.E[curr]:
            dfs(child)

        c, i, v = event[var["e"]-1]
        if event[var["e"]-1] != None and c == curr:
            dp[i] = v
            var["e"] -= 1

    dfs(0)
    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: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
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)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            idx = bin_search(dp[:len(paths)+1], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a, 1))
                dp[len(paths)] = a
                ddp2[0] += 1
            else:
                if dp[idx] == float('inf'):
                    actions.append((idx, dp[idx], a, 1))
                    ddp2[0] += 1
                else:
                    actions.append((idx, dp[idx], a, 0))
                dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()