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)