Codeforces Round 498(Div.3) E. Military Problem
問題概要
頂点の根付き木が与えられる。根は1である。
ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与える。命令が葉まで伝搬すると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与えることを繰り返す。
個のクエリが与えられる。 番目のクエリでは頂点 に命令を与えた時に 番目に命令が伝えられる頂点を答える。
制約
解法
事前に頂点0からDFSをして、命令が伝わる順番を計算しておく。このとき、ある頂点に命令が伝わる順番を記録しておくことによって、各クエリにで答えることができる。
全体の計算量は