#1192874 (PyPy3) No.2325 Skill Tree

• 問題: No.2325 Skill Tree
• ユーザー: LyricalMaestro
• 提出日時: 2026-10-11 15:46:50
• 言語: PyPy3 (8.0.0 + ACL)
• 結果: AC
• 実行時間: 388 ms / 3,000 ms
• コード長: 3,342 bytes
• コンパイル時間: 74 ms
• コンパイル使用メモリ: 81,536 KB
• 実行使用メモリ: 130,908 KB
• 最終ジャッジ日時: 2026-10-11 15:47:17
• 合計ジャッジ時間: 20,720 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 36

ソースコード

## https://yukicoder.me/problems/no/2325

from collections import deque

MAX_INT = 10 ** 18


class BinaryIndexTree:
    """
    フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス
    """
    def __init__(self, size):
        self.size = size
        self.array = [0] * (size + 1)
    
    def add(self, x, a):
        index = x
        while index <= self.size:
            self.array[index] += a
            index += index & (-index)
    
    def sum(self, x):
        index = x
        ans = 0
        while index > 0:
            ans += self.array[index]
            index -= index & (-index)
        return ans

    def least_upper_bound(self, value):
        if self.sum(self.size) < value:
            return -1
        elif value <= 0:
            return 0

        m = 1
        while m < self.size:
            m *= 2

        k = 0
        k_sum = 0
        while m > 0:
            k0 = k + m
            if k0 < self.size:
                if k_sum + self.array[k0] < value:
                    k_sum += self.array[k0]
                    k += m
            m //= 2
        if k < self.size:
            return k + 1
        else:
            return -1


def main():
    N = int(input())
    la = []
    for _ in range(N - 1):
        l, a = map(int, input().split())
        la.append((l, a - 1))
    Q = int(input())
    queries = []
    for _ in range(Q):
        t, x = map(int, input().split())
        queries.append((t, x))

    # トポロジカルソートとDP
    next_nodes= [[] for _ in range(N)]
    levels = [-1] * N
    levels[0] = 0
    in_degree = [0] * N
    for i in range(N - 1):
        l, a = la[i]
        levels[i + 1] = l
        next_nodes[a].append(i + 1)
        in_degree[i + 1] += 1

    dp = [MAX_INT] * N
    queue = deque()
    for i in range(N):
        if in_degree[i] == 0:
            queue.append(i)
            dp[i] = levels[i]

    while len(queue) > 0:
        v = queue.popleft()

        for w in next_nodes[v]:
            in_degree[w] -= 1
            if dp[w] == MAX_INT:
                dp[w] = levels[w]

            dp[w] = max(dp[v], dp[w])
            if in_degree[w] == 0:
                queue.append(w)

    # レベルXが覚えられる技をカウントするためのもの
    a_map = {}
    for i in range(N):
        d = dp[i]
        if d < MAX_INT:
            if d not in a_map:
                a_map[d] = 0
            a_map[d] += 1
    a_array = [(key, value) for key, value in a_map.items()]
    a_array.sort(key=lambda x : x[0])
    a_cum_values = [0] * len(a_array)
    a = 0
    for i in range(len(a_array)):
        a += a_array[i][1]
        a_cum_values[i] = a

    # 実際の計算
    for t, x in queries:
        if t == 2:
            x -= 1
            v = dp[x]
            if v == MAX_INT:
                print(-1)
            else:
                print(v)
        else:
            low = 0
            high = len(a_array) - 1
            while high - low > 1:
                mid = (high + low) // 2
                if a_array[mid][0] <= x:
                    low = mid
                else:
                    high = mid
            if a_array[high][0] <= x:
                print(a_cum_values[high])
            else:
                print(a_cum_values[low])

    
    



if __name__ == "__main__":
    main()