AtCoder Beginner Contest 239 E - Subtree K-th Max【Python】
https://atcoder.jp/contests/abc239/tasks/abc239_e
AtCoder ProblemsでDifficulty: 1084、Solve Probability: 10%でした。
解けませんでした。クエリのKの制約が20以下のため、部分木に含まれる頂点に書かれた数のリストの長さは20まで持っておけば良いという事に気づきませんでした。
import sys sys.setrecursionlimit(10 ** 7) N, Q = map(int, input().split()) X = list(map(int, input().split())) G = [[] for _ in range(N)] for i in range(N-1): a, b = map(int, input().split()) a-=1 b-=1 G[a].append(b) G[b].append(a) visited = [False]*N ans = [] for i in range(N): a = list() ans.append(a) def dfs(i): global ans visited[i] = True ans[i].append(X[i]) for i2 in G[i]: if not visited[i2]: dfs(i2) ans[i] += ans[i2] ans[i] = sorted(ans[i], reverse=True)[:20] dfs(0) for i in range(Q): v, k= map(int, input().split()) v-=1 k-=1 print(ans[v][k])