AtCoder Beginner Contest 239 E

https://atcoder.jp/contests/abc239/tasks/abc239_e

Kに制限があるところが全てですね。ちゃんと読まないとそんなのがあると思わない。

# coding: utf-8
# Subtree K-th Max

from itertools import *
from collections import defaultdict
import sys

sys.setrecursionlimit(2*10**5)


#################### library ####################

def read_tuple():
    return tuple(map(int, raw_input().split()))

def read_list():
    return list(map(int, raw_input().split()))

def classify(iterable):
    dic = defaultdict(list)
    for k, v in iterable:
        dic[k].append(v)
    return dic


#################### Node ####################

class Node:
    def __init__(self, i, value):
        self.i          = i
        self.value      = value
        self.children   = []
        self.values     = []
    
    def is_leaf(self):
        return not self.children
    
    @staticmethod
    def make_tree(edges, X):
        N = len(X)
        nodes = [None] + [ Node(i, value) for i, value in enumerate(X, 1) ]
        dic = classify(edge for A, B in edges for edge in [(A, B), (B, A)])
        stack = [1]
        finished = set()
        while stack:
            i = stack.pop()
            nodes[i].children.extend(j for j in dic[i] if j not in finished)
            finished.add(i)
            stack.extend(nodes[i].children)
        
        nodes[1].__make_values(nodes)
        return nodes
    
    def __make_values(self, nodes):
        self.values.append(self.value)
        if not self.is_leaf():
            for j in self.children:
                child = nodes[j]
                child.__make_values(nodes)
                self.values.extend(child.values)
            self.values.sort()
            self.values = self.values[-max_K:]


#################### process ####################

def read_input():
    N, Q = read_tuple()
    X = read_list()
    edges = [ read_tuple() for _ in range(N-1) ]
    queries = [ read_tuple() for _ in range(Q) ]
    return (X, edges, queries)

def F(X, edges, queries):
    nodes = Node.make_tree(edges, X)
    for V, K in queries:
        print nodes[V].values[-K]


#################### main ####################

max_K = 20
X, edges, queries = read_input()
F(X, edges, queries)