足跡-sokuseki-

りかの日進月歩の記録

Codeforces Round 498(Div.3) E. Military Problem

Problem - E - Codeforces

問題概要

 N 頂点の根付き木が与えられる。根は1である。
ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与える。命令が葉まで伝搬すると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与えることを繰り返す。

 q 個のクエリが与えられる。 i 番目のクエリでは頂点  u_i に命令を与えた時に k_i 番目に命令が伝えられる頂点を答える。

制約

 1 \le N, q \le 2 \times 10^5

解法

事前に頂点0からDFSをして、命令が伝わる順番を計算しておく。このとき、ある頂点に命令が伝わる順番を記録しておくことによって、各クエリに O(1) で答えることができる。
全体の計算量は  O(q)

Submission #40441251 - Codeforces