No.897 compαctree
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 344
作問者 : niuez / テスター : Lemma299 polylogK
タグ : / 解いたユーザー数 344
作問者 : niuez / テスター : Lemma299 polylogK
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。