コンテスト中AC:A〜E

B - Intenger Division

以前、このような自作関数を作っていました。

template<typename T> 
T Floor(T a, T b) {
    if ((a<0 && b<0) || (a>0 && b>0)) return a/b;
    else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL;
}

これを使うことで、Floor(X,10LL)で求められました。
提出コード

E - Subtree K-th Max

Kが小さいことから、公式解説の想定解を思いつきつつも、計算量の見積もりがよくわからなかったので、異なる解法で解きました。
オイラーツアーの部分木クエリと同じ考え方となります。

まず、一回のDFSで以下を記録しておきます。

頂点 $u_i$ のpre-order順。これを $Id_u$ とします。
$X_i$ を頂点のpre-order順に並べたもの。これを配列 $A$ とします。
部分木に属する頂点数。これを $dp_u$ とします。

このようにすると、 $i$ 番目のクエリは、

$Id_{V_i} \leq j \lt Id_{V_i}+dp_{V_i}$ を満たす $A_j$ のうち $K_i$ 番目に大きい数を求めよ

という問題となります。入力例1を例にします。以下はDFS実行後の一例です。

$A = \{1,4,2,5,3\}$
$Id = \{1,3,5,2,4\}$
$dp = \{5,3,1,1,1\}$

ここで、2個目のクエリ、頂点2を根とした時の1番目に大きい数を求めてみます。
対象となる $A_j$ の区間は、 $3\leq j \lt 3+3 \rightarrow 3\leq j \lt 6$ となるので、 $A_3,A_4,A_5$ から1番目に大きい値を計算します。
$2,3,5$ なので、答えは $5$ です。