結果
| 問題 | No.2325 Skill Tree |
| ユーザー |
 ngng628
|
| 提出日時 | 2023-05-28 15:04:26 |
| 言語 | Crystal (1.11.2) |
| 結果 |
AC
|
| 実行時間 | 1,162 ms / 3,000 ms |
| コード長 | 24,009 bytes |
| コンパイル時間 | 23,033 ms |
| コンパイル使用メモリ | 265,448 KB |
| 実行使用メモリ | 135,960 KB |
| 最終ジャッジ日時 | 2023-08-27 11:23:15 |
| 合計ジャッジ時間 | 55,441 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
4,428 KB |
| testcase_01 | AC | 3 ms
4,476 KB |
| testcase_02 | AC | 2 ms
4,460 KB |
| testcase_03 | AC | 3 ms
4,444 KB |
| testcase_04 | AC | 3 ms
4,452 KB |
| testcase_05 | AC | 3 ms
4,436 KB |
| testcase_06 | AC | 2 ms
4,580 KB |
| testcase_07 | AC | 356 ms
48,204 KB |
| testcase_08 | AC | 312 ms
50,580 KB |
| testcase_09 | AC | 449 ms
48,892 KB |
| testcase_10 | AC | 454 ms
74,636 KB |
| testcase_11 | AC | 491 ms
56,328 KB |
| testcase_12 | AC | 1,002 ms
110,092 KB |
| testcase_13 | AC | 1,016 ms
109,792 KB |
| testcase_14 | AC | 1,022 ms
109,544 KB |
| testcase_15 | AC | 1,054 ms
104,116 KB |
| testcase_16 | AC | 1,046 ms
104,148 KB |
| testcase_17 | AC | 905 ms
110,032 KB |
| testcase_18 | AC | 924 ms
104,236 KB |
| testcase_19 | AC | 915 ms
108,868 KB |
| testcase_20 | AC | 923 ms
110,092 KB |
| testcase_21 | AC | 899 ms
110,116 KB |
| testcase_22 | AC | 1,083 ms
108,520 KB |
| testcase_23 | AC | 1,131 ms
110,224 KB |
| testcase_24 | AC | 1,145 ms
135,960 KB |
| testcase_25 | AC | 1,111 ms
110,028 KB |
| testcase_26 | AC | 1,107 ms
108,436 KB |
| testcase_27 | AC | 1,033 ms
109,668 KB |
| testcase_28 | AC | 1,040 ms
109,280 KB |
| testcase_29 | AC | 1,054 ms
109,196 KB |
| testcase_30 | AC | 1,067 ms
104,048 KB |
| testcase_31 | AC | 1,058 ms
109,440 KB |
| testcase_32 | AC | 925 ms
108,208 KB |
| testcase_33 | AC | 935 ms
108,072 KB |
| testcase_34 | AC | 938 ms
109,104 KB |
| testcase_35 | AC | 1,162 ms
108,604 KB |
| testcase_36 | AC | 1,112 ms
123,276 KB |
| testcase_37 | AC | 1,160 ms
108,580 KB |
ソースコード
def int(b = 0)
read_line.to_i64 + b
end
def ints(b = 0)
read_line.split.map { |x| x.to_i64 + b }
end
def str
read_line.chomp
end
macro chmax(a, b)
({{a}} < {{b}} && ({{a}} = {{b}}))
end
macro chmin(a, b)
({{a}} > {{b}} && ({{a}} = {{b}}))
end
macro make_array(s, x)
Array.new({{ s[0] }}) {
{% if s[1..s.size].empty? %}; {{ x }}
{% else %}; make_array({{ s[1..s.size] }}, {{ x }}) {% end %}
}
end
OO = (1_i64 << 62) - (1_i64 << 31)
module NgLib
# 不変な数列 $A$ に対して、$\sum_{i=l}^{r-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。
class StaticRangeSum(T)
getter size : Int64
getter csum : Array(T)
# 配列 `array` に対して累積和を構築します。
#
# ```
# array = [1, 1, 2, 3, 5, 8, 13]
# csum = StaticRangeSum(Int32).new(array)
# ```
def initialize(array : Array(T))
@size = array.size.to_i64
@csum = Array.new(@size + 1, T.zero)
@size.times { |i| @csum[i + 1] = @csum[i] + array[i] }
end
# $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
#
# ```
# array = [1, 1, 2, 3, 5, 8, 13]
# csum = StaticRangeSum(Int32).new(array)
# csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
# ```
def get(l, r) : T
raise IndexError.new("`l` must be less than or equal to `r` (#{l}, #{r})") unless l <= r
@csum[r] - @csum[l]
end
# :ditto:
def get(range : Range(Int?, Int?)) : T
l = (range.begin || 0)
r = if range.end.nil?
@size
else
range.end.not_nil! + (range.exclusive? ? 0 : 1)
end
get(l, r)
end
# $[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
#
# $l \leq r$ を満たさないとき、`nil` を返します。
#
# ```
# array = [1, 1, 2, 3, 5, 8, 13]
# csum = StaticRangeSum(Int32).new(array)
# csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
# csum.get?(7...5) # => nil
# ```
def get?(l, r) : T?
return nil unless l <= r
get(l, r)
end
# :ditto:
def get?(range : Range(Int?, Int?)) : T?
l = (range.begin || 0)
r = if range.end.nil?
@size
else
range.end.not_nil! + (range.exclusive? ? 0 : 1)
end
get?(l, r)
end
# $\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。
def get!(l, r) : T
@csum[r] - @csum[l]
end
# :ditto:
def get!(range : Range(Int?, Int?)) : T
l = (range.begin || 0)
r = if range.end.nil?
@size
else
range.end.not_nil! + (range.exclusive? ? 0 : 1)
end
get!(l, r)
end
# `get(l : Int, r : Int)` へのエイリアスです。
def [](l, r) : T
get(l, r)
end
# `get(range : Range(Int?, Int?))` へのエイリアスです。
def [](range : Range(Int?, Int?)) : T
get(range)
end
# `get(l : Int, r : Int)` へのエイリアスです。
def []?(l, r) : T?
get?(l, r)
end
# `get?(range : Range(Int?, Int?))` へのエイリアスです。
def []?(range : Range(Int?, Int?)) : T?
get?(range)
end
end
end
module NgLib
# 不変な数列 $A$ について、以下の条件を満たす演算を、区間クエリとして処理します。
# - 結合則 : $(x \oplus y) \oplus z = x \oplus (y \oplus z)$
# - 冪等性 : $x \oplus x = x$
#
# 前計算は $O(N \log{N})$ かかりますが、区間クエリには $O(1)$ で答えられます。
class SparseTable(T)
getter size : Int32
@data : Array(T)
@table : Array(Array(T))
@lookup : Array(Int32)
@op : (T, T) -> T
# $\oplus = \max$ としてデータ構造を構築します。
def self.max(elems : Enumerable(T))
new elems, ->(x : T, y : T) { x > y ? x : y }
end
# $\oplus = \min$ としてデータ構造を構築します。
def self.min(elems : Enumerable(T))
new elems, ->(x : T, y : T) { x < y ? x : y }
end
# $\oplus = \mathrm{bitwise-or}$ としてデータ構造を構築します。
def self.bitwise_or(elems : Enumerable(T))
new elems, ->(x : T, y : T) { x | y }
end
# $\oplus = \mathrm{bitwise-and}$ としてデータ構造を構築します。
def self.bitwise_and(elems : Enumerable(T))
new elems, ->(x : T, y : T) { x & y }
end
# $\oplus = \mathrm{gcd}$ としてデータ構造を構築します。
def self.gcd(elems : Enumerable(T))
new elems, ->(x : T, y : T) { x.gcd(y) }
end
# $\oplus = op$ としてデータ構造を構築します。
def initialize(elems : Enumerable(T), @op : (T, T) -> T)
@size = elems.size
@data = Array(T).new
log = (0..).index! { |k| (1 << k) > @size }
@table = Array.new(log) { Array(T).new(1 << log, T.zero) }
elems.each_with_index { |e, i| @table[0][i] = e; @data << e }
(1...log).each do |i|
j = 0
while j + (1 << i) <= (1 << log)
@table[i][j] = @op.call(@table[i - 1][j], @table[i - 1][j + (1 << (i - 1))])
j += 1
end
end
@lookup = [0] * (@size + 1)
(2..@size).each do |i|
@lookup[i] = @lookup[i >> 1] + 1
end
end
# `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。
#
# ```
# rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
# rmq.prod(0...3) # => 1
# ```
def prod(range : Range(Int?, Int?))
l = (range.begin || 0)
r = if range.end.nil?
@size
else
range.end.not_nil! + (range.exclusive? ? 0 : 1)
end
b = @lookup[r - l]
@op.call(@table[b][l], @table[b][r - (1 << b)])
end
# `range` の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。
#
# $0 \leq l \leq r \leq n$ を満たさないとき、`nil` を返します。
#
# ```
# rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
# rmq.prod(0...3) # => 1
# ```
def prod?(range : Range(Int?, Int?))
l = (range.begin || 0)
r = if range.end.nil?
@size
else
range.end.not_nil! + (range.exclusive? ? 0 : 1)
end
return nil unless 0 <= l && l <= r && r <= @size
prod(range)
end
# $a_i$ を返します。
def [](i)
@data[i]
end
# $a_i$ を返します。
#
# 添字が範囲外のとき、`nil` を返します。
def []?(i)
@data[i]?
end
# `prod` へのエイリアスです。
def [](range : Range(Int?, Int?))
prod(range)
end
# `prod?` へのエイリアスです。
def []?(range : Range(Int?, Int?))
prod?(range)
end
end
end
class StronglyConnectedComponents
alias Graph = Array(Array(Int64))
getter leader : Array(Int64)
getter graph : Graph
getter groups : Array(Array(Int64))
@n : Int64
@order : Array(Int64)
@fwd : Graph
@bwd : Graph
@closed : Array(Bool)
def initialize(@fwd : Graph)
@n = @fwd.size.to_i64
@order = Array(Int64).new(@n)
@leader = Array.new(@n, -1_i64)
@bwd = Array.new(@n){ Array(Int64).new }
@n.times do |i|
@fwd[i].each do |j|
@bwd[j] << i
end
end
@closed = Array(Bool).new(@n, false)
@n.times{ |i| dfs(i) }
@order = @order.reverse
ptr = rdfs
@graph = Array.new(ptr){ Array(Int64).new }
@groups = Array.new(ptr){ Array(Int64).new }
@n.times do |i|
@groups[@leader[i]] << i
@fwd[i].each do |j|
x, y = @leader[i], @leader[j]
next if x == y
@graph[x] << y
end
end
end
def same(u : Int, v : Int)
leader[u] == leader[v]
end
def size
@groups.size
end
def size(v : Int)
@groups[leader[v]].size
end
private def dfs(i : Int)
return if @closed[i]
@closed[i] = true
@fwd[i].each{ |j| dfs(j) }
@order << i
end
private def rdfs
ptr = 0_i64
closed = Array.new(@n, false)
@order.each do |s|
next if closed[s]
que = Deque(Int64).new
que << s
closed[s] = true
@leader[s] = ptr
until que.empty?
now = que.shift
@bwd[now].each do |nxt|
next if closed[nxt]
closed[nxt] = true
@leader[nxt] = ptr
que << nxt
end
end
ptr += 1
end
ptr
end
end
struct Int64
def self.inf
OO
end
end
module NgLib
struct Edge
@data : {Int64, Int64}
def initialize(t : Int64, w : Int64)
@data = {t, w}
end
def self.to
@data[0]
end
def self.weight
@data[1]
end
def [](i : Int)
@data[i]
end
end
end
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr
#
# Copyright 2023 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
module AtCoder
# Implements standard priority queue like [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue).
#
# ```
# q = AtCoder::PriorityQueue(Int64).new
# q << 1_i64
# q << 3_i64
# q << 2_i64
# q.pop # => 3
# q.pop # => 2
# q.pop # => 1
# ```
class PriorityQueue(T)
include Enumerable(T)
getter heap : Array(T)
# Create a new queue in ascending order of priority.
def self.max
self.new { |a, b| a <= b }
end
# Create a new queue in ascending order of priority with the elements in *enumerable*.
def self.max(enumerable : Enumerable(T))
self.new(enumerable) { |a, b| a <= b }
end
# Create a new queue in descending order of priority.
def self.min
self.new { |a, b| a >= b }
end
# Create a new queue in descending order of priority with the elements in *enumerable*.
def self.min(enumerable : Enumerable(T))
self.new(enumerable) { |a, b| a >= b }
end
def initialize
initialize { |a, b| a <= b }
end
# Initializes queue with the elements in *enumerable*.
def self.new(enumerable : Enumerable(T))
self.new(enumerable) { |a, b| a <= b }
end
# Initializes queue with the custom comperator.
#
# If the second argument `b` should be popped earlier than
# the first argument `a`, return `true`. Else, return `false`.
#
# ```
# q = AtCoder::PriorityQueue(Int64).new { |a, b| a >= b }
# q << 1_i64
# q << 3_i64
# q << 2_i64
# q.pop # => 1
# q.pop # => 2
# q.pop # => 3
# ```
def initialize(&block : T, T -> Bool)
@heap = Array(T).new
@compare_proc = block
end
# Initializes queue with the elements in *enumerable* and the custom comperator.
#
# If the second argument `b` should be popped earlier than
# the first argument `a`, return `true`. Else, return `false`.
#
# ```
# q = AtCoder::PriorityQueue.new([1, 3, 2]) { |a, b| a >= b }
# q.pop # => 1
# q.pop # => 2
# q.pop # => 3
# ```
def initialize(enumerable : Enumerable(T), &block : T, T -> Bool)
@heap = enumerable.to_a
@compare_proc = block
len = @heap.size
(len // 2 - 1).downto(0) do |parent|
v = @heap[parent]
child = parent * 2 + 1
while child < len
if child + 1 < len && @compare_proc.call(@heap[child], @heap[child + 1])
child += 1
end
unless @compare_proc.call(v, @heap[child])
break
end
@heap[parent] = @heap[child]
parent = child
child = parent * 2 + 1
end
@heap[parent] = v
end
end
# Pushes value into the queue.
def push(v : T)
@heap << v
index = @heap.size - 1
while index != 0
parent = (index - 1) // 2
if @compare_proc.call(@heap[index], @heap[parent])
break
end
@heap[parent], @heap[index] = @heap[index], @heap[parent]
index = parent
end
end
# Alias of `push`
def <<(v : T)
push(v)
end
# Pops value from the queue.
def pop
if @heap.size == 0
return nil
end
if @heap.size == 1
return @heap.pop
end
ret = @heap.first
@heap[0] = @heap.pop
index = 0
while index * 2 + 1 < @heap.size
child = if index * 2 + 2 < @heap.size && !@compare_proc.call(@heap[index * 2 + 2], @heap[index * 2 + 1])
index * 2 + 2
else
index * 2 + 1
end
if @compare_proc.call(@heap[child], @heap[index])
break
end
@heap[child], @heap[index] = @heap[index], @heap[child]
index = child
end
ret
end
# Yields each item in the queue in comparator's order.
def each(&)
@heap.sort { |a, b| @compare_proc.call(a, b) ? 1 : -1 }.each do |e|
yield e
end
end
# Returns, but does not remove, the head of the queue.
def first(&)
@heap.first { yield }
end
# Returns `true` if the queue is empty.
delegate :empty?, to: @heap
# Returns size of the queue.
delegate :size, to: @heap
end
end
module NgLib
abstract struct Weight
include Comparable(Weight)
def self.zero : self
end
def self.inf : self
end
def +(other : self)
end
def <=>(other : self)
end
end
class DijkstraGraph(Weight)
record Edge(W), target : Int32, weight : W
getter size : Int32
@graph : Array(Array(Edge(Weight)))
# $n$ 頂点 $0$ 辺からなるグラフを作成します。
#
# ```
# graph = Dijkstra.new(n)
# ```
def initialize(n : Int)
@size = n.to_i32
@graph = Array.new(@size) { Array(Edge(Weight)).new }
end
# 非負整数の重み $w$ の辺 $(u, v)$ を追加します。
#
# `directed` が `true` の場合、
# 有向辺とみなして、$u$ から $v$ への辺のみ生やします。
#
# ```
# graph = Dijkstra.new(n)
# graph.add_edge(u, v, w) # => (u) <---w---> (v)
# graph.add_edge(u, v, w, directed: true) # => (u) ----w---> (v)
# ```
def add_edge(u : Int, v : Int, w : Weight, directed : Bool = false)
@graph[u.to_i32] << Edge.new(v.to_i32, w)
@graph[v.to_i32] << Edge.new(u.to_i32, w) unless directed
end
# 全点対間の最短経路長を返します。
#
# ```
# dists = graph.shortest_path
# dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]
# ```
def shortest_path : Array(Array(Weight))
(0...@size).map { |s| shortest_path(s) }
end
# 始点 `start` から各頂点への最短経路長を返します。
#
# ```
# dist = graph.shortest_path(2)
# dist # => [3, 8, 0, 7, 1]
# ```
def shortest_path(start : Int) : Array(Weight)
dist = [Weight.inf] * @size
dist[start] = Weight.zero
next_node = AtCoder::PriorityQueue({Weight, Int32}).min
next_node << {Weight.zero, start.to_i32}
until next_node.empty?
d, source = next_node.pop.not_nil!
next if dist[source] < d
@graph[source].each do |e|
next_cost = dist[source] + e.weight
if next_cost < dist[e.target]
dist[e.target] = next_cost
next_node << {next_cost, e.target}
end
end
end
dist
end
# 始点 `start` から終点 `dest` への最短経路長を返します。
#
# ```
# dist = graph.shortest_path(start: 2, dest: 0)
# dist # => 12
# ```
def shortest_path(start : Int, dest : Int) : Weight
shortest_path(start)[dest]
end
# 始点 `start` から終点 `dest` への最短経路の一例を返します。
#
# ```
# route = graph.shortest_path_route(start: 2, dest: 0)
# route # => [2, 7, 1, 0]
# ```
def shortest_path_route(start, dest)
prev = impl_memo_route(start)
res = Array(Int32).new
now : Int32? = dest.to_i32
until now.nil?
res << now.not_nil!
now = prev[now]
end
res.reverse
end
# 始点 `start` から最短路木を構築します。
#
# 最短路木は `start` からの最短経路のみを残した全域木です。
#
# ```
# route = graph.shortest_path_route(start: 2, dest: 0)
# route # => [2, 7, 1, 0]
# ```
def shortest_path_tree(start, directed : Bool = false) : Array(Array(Int32))
dist = [Weight.inf] * @size
dist[start] = Weight.zero
next_node = AtCoder::PriorityQueue({Weight, Int32}).min
next_node << {Weight.zero, start.to_i32}
birth = [-1] * @size
until next_node.empty?
d, source = next_node.pop.not_nil!
next if dist[source] < d
@graph[source].each do |e|
next_cost = dist[source] + e.weight
if next_cost < dist[e.target]
dist[e.target] = next_cost
next_node << {next_cost, e.target}
birth[e.target] = source
end
end
end
tree = Array.new(@size) { [] of Int32 }
@size.times do |target|
source = birth[target]
next if source == -1
tree[source] << target
tree[target] << source unless directed
end
tree
end
# 経路復元のための「どこから移動してきたか」を
# メモした配列を返します。
private def impl_memo_route(start)
dist = [Weight.inf] * @size
dist[start] = Weight.zero
prev = Array(Int32?).new(@size) { nil }
next_node = AtCoder::PriorityQueue({Weight, Int32}).min
next_node << {Weight.zero, start.to_i32}
until next_node.empty?
d, source = next_node.pop.not_nil!
next if dist[source] < d
@graph[source].each do |e|
next_cost = dist[source] + e.weight
if next_cost < dist[e.target]
dist[e.target] = next_cost
prev[e.target] = source
next_node << {next_cost, e.target}
end
end
end
prev
end
end
end
class Array(T)
def compress
b = clone.sort.uniq
map{ |s| b.bsearch_index{ |x| x >= s } || b.size }
end
def mapping
b = clone.sort.uniq
f, g = Hash(Int64, Int64).new, Hash(Int64, Int64).new
each do |s|
index = b.bsearch_index{ |x| x >= s } || b.size
f[s] = index
g[index] = s
end
{f, g}
end
end
# .O,
# :o.
# 'd' :c;. c
# lc dKl ;d,.,cl:. oOx.
# .x. .,. 'd:.......:ll;. 'lc
# .;0; .ol............'col;.
# .:do;xl cd'.................,col;.
# .,cdd:' od 'x;........:..............':ol;.
# ..;lddc,. od od....l:...;x.........,........,lo;
# .,:loodl;. .,,kx. .kk:....k,...lo........od.........;.:x,
# .,coool:,. ....;lkodl....O:...dk.......;Oo........:x...oo
# :dl;'. .lk:...Ok...xkc......xcx.......,k'....:x
# ;k, :x:.Olx'.O'd;....;o.O......;Oc......cx
# O, . ;xO;.cOO..ll,..l: x,...,dck,.......dc
# k: lKd oO. KK .;cld; dc;lOc.;d........,0
# dl . cx.cO. .,.KW..x'.........0.
# oc .ll;. :k.l: ;l,k,...;:.....0.
# o, kkxkOOOOOOOOOkkkkxl:'. ;x.,. .dOoccod:.....cO
# x..o. lOxxxxxxxxxxxxxxxxxxkXOOdc' oc .l;,,,;coo:...ol......o0,
# O ' xOxxxxxxxxxxxxxxxxxxxxKOxxkOOd; .0. '0:ccc:,,,0ccd;....;lx0l
# .x .Okxxxxxxxxxxxxxxxxxxxxx0KxxxxxxkOo. O' do'''''''OllOkoooolckl
# ;l .OkxxxxxxxxxxxxxxxxxxxxxxOKxxxxxkOxk0l kkollll0kdoddxkK0Oxllooool.
# c: kKxxxxxxxxxxxxxxxxxxxxxxx0XkxxxxkXxxxOO k' ;d. .k,....':ok0dc;.. .'::
# o, xO00xxxxxxxxxxxxxxxxxxxxxxKOKxxxxxXdoOk0; .O ;d .k. .cd,ckccc;lx,
# d, c0xx0Kkxxxxxxxxxxxxxxxxxxx0O.KkxxxkX. .0K; lk:lOo;;Oo;kd; ' .x;:c .
# d, .0KxxxkK0kxxxxxxxxxxxxxxxx0k. l0xxxOx O0 'O::k; .kckO: Okollxxkx. k.
# d, xod0xxxxK00OxxxxxxxxxxxxO0l. 'XxxkK' ;K, .Oxxo. .o x: ;O;;xo..K. l:
# l; 0:;d0xxxkO.;ok0OkO00OkO0l. KkkKc';d0, ;olxx ,dd; 'Kkkk, 'Oc 'x
# :l K:;;o0kxxKc .':c..:o,. O0OlO0Kd. 'ol. :d lO' ;00x;. ck' O.
# 'x 0c;;;cO0xkXk, '. cdk00x..cOx ol .od. ,c. 'k; d;
# 0. kl;;;;;oO0OK0, ,ccO00KOokk.'x. o: 'cx0; .::c:. od ;d
# ;d..xd:;;;;;cdkkk,... ..';llc::,... ;d..xkc .klld. ol ol .k
# ,llokkolcccloddkK0K00ck00xodoo:. cl ' .o..d: c. ,k k.
# .,:c::;,.. ;d .0;k. ;lodxkKo .d' :x;'.....:xc lc
# lx :OOOol 'O :o. dOooodd0. .O
# lxc:,k:O .d; ll .dc ld;;;;O' l;
# .c, dk:k;.k oOcc,,O. ,x. Oc;;;x: x.
# .ld.'lkd;,:cdlc;;0, .:' dxcc:;,'kdllld0;',.. ;loodoool
# ,ol. .oo. ...' .:::cccl:. :x. .............';codOc;;;;;;;;
# :kd, co .'c, 'k. ,dx:;;;;;;
# .:llld;,;:....O' .x: .ko;;;;;;
# 'lkcodxdxO. ;x, :kc;;;;;;
# ;k;;;;;;dx o0' ;Kd;;;;;
n = int
skills = (1..n - 1).map { ints }
q = int
queries = (1..q).map { ints }
graph = Array.new(n) { [] of NgLib::Edge }
scc_graph = Array.new(n) { [] of Int64 }
skills.each_with_index do |(l, a), i|
graph[a - 1] << NgLib::Edge.new(i + 1, l)
scc_graph[a - 1] << i + 1
end
scc = StronglyConnectedComponents.new(scc_graph)
# 技 i を覚えるのに必要な最小コスト
dist = [-OO] * n
dist[0] = 0
queue = Deque({Int64, Int64}).new
queue << {0_i64, -1_i64}
until queue.empty?
from, par = queue.pop
graph[from].each do |(to, w)|
next if to == par
chmax(dist[to], Math.max(dist[from], w))
queue << {to, from}
end
end
n.times do |i|
dist[i] = OO if dist[i] == -OO
dist[i] = OO if scc.size(i) >= 2
end
# 技 i を覚えるための最小コスト
rmq = NgLib::SparseTable(Int64).max(dist)
# レベル x 以下の技は何個？
lvs = [] of Int64
queries.each do |(t, x)|
lvs << x if t == 1
end
f, g = (dist + lvs).mapping
cnt = [0_i64] * f.size
dist.each_with_index do |lv, i|
cnt[f[lv]] += 1
end
csum = NgLib::StaticRangeSum(Int64).new(cnt)
queries.each do |(t, x)|
y = x
case t
when 1
ans = csum[0..f[x]]
puts ans
when 2
ans = dist[y - 1]
puts ans >= OO ? -1 : ans
end
end