AtCoderBeginnerContest239 E問題500点 「Subtree K-th Max」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^5
気持ち
解法
「ある頂点$ V_iの部分木の頂点のうち、$ K_i番目に大きい頂点を求める」というクエリ問題です。
ここで、「部分木」という性質から「葉（もっとも下側にある頂点）」から再帰的にクエリを処理すれば良いという気持ちになります。
https://gyazo.com/2363be6fa6ae275bbeed51a59d0a96e4
子供の部分木から「子供が含むすべての$ X_iの値」をマージしながら親に返していけばいいです。
たとえば、以下の図では、値4 を持つノードの再帰関数では「値2を持つ子ノード と 値6,3,5を持つ子ノード」をマージして「4, 2, 6, 3, 5」を、値4 を持つノードが管理すればよいです。
https://gyazo.com/694d8e66f1747ec5a27776000a5cde3c
ただし、これを実際にすべてのノードに対して行うと、最大ノード数が$ Nあるため$ N^2かかってしまいます。
そこで、制約に注目します。
大きい方から$ k番目の制約では、最大が$ K_i = 20番目です。
よって、上位$ 20個だけを常にもつようにマージすれば、計算量が非常に小さくなります。
計算量
$ O(NC)
ただし、$ Cは$ \max(K_i)
新たな学び
ちゃんと制約を見てからコーディングする
Go でも自己再帰関数を lambda でかける
先に var で宣言しておく
そのため、型は2回書く必要がある
反省点
コード
code: go
func Min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
type UnWeightedGraph [][]int
func solve() {
N, Q := mio.NextInt(), mio.NextInt()
X := make([]int, N)
for i := 0; i < N; i++ {
}
var G UnWeightedGraph = make([][]int, N)
for i := 0; i < N-1; i++ {
a, b := mio.NextInt(), mio.NextInt()
a--
b--
}
queries := make([][]2int, N) for i := 0; i < Q; i++ {
v, k := mio.NextInt(), mio.NextInt()
v--
queriesv = append(queriesv, 2int{k, i}) }
ans := make([]int, Q)
var dfs func(v int, p int) []int
dfs = func(v int, p int) []int {
dp := make([]int, 0)
if to == p {
continue
}
ret := dfs(to, v)
for _, x := range ret {
dp = append(dp, x)
}
}
sort.Slice(dp, func(i, j int) bool { return dpi > dpj }) for _, q := range queriesv { }
return dp
}
dfs(0, -1)
for i := 0; i < Q; i++ {
}
}