問題一覧 > 通常問題

No.897 compαctree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 344
作問者 : niuezniuez / テスター : Lemma299Lemma299 polylogKpolylogK
4 ProblemId : 3403 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-04 21:31:43

問題文

niuez くんは木を美しく作る技術を持っており,美しい木を求める客から依頼を受けています.
niuez くんの住む街ではコンパクトな木(compactree)が流行っており,それを作成する query を niuez くんは大量に預かっています.
次の $Q$ 個の query を処理してください.

  • $N \ K$
    • $N$ 個の頂点と$N-1$個の辺からなる $K$ 分有向木(すべての頂点の子が高々 $K$ 個であるような木)のうち,深さの最小値を求める.
    • ここで,深さとは根から各頂点へのパスに含まれる辺の数のうち,最大のものを指します.

入力

$Q$
$N_0\ K_0$
$\cdots$
$N_{Q-1}\ K_{Q-1}$
  • $1 \leq Q \leq 10$
  • $1 \leq N_i, K_i \leq 10^9$
  • 入力はすべて整数

出力

$Q$ 行出力し,$i$ 行目には $i$ 番目の ${\rm query}$ の答えを整数で一行に出力してください.

サンプル

サンプル1
入力
3
4 2
41 3
100 1
出力
2
4
99

最初のクエリは例えば以下のように木をつくると高さを2にできます.
子の数は頂点$2$の2個が最大で, 入力の条件を満たしています.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。