以下の問題を考えましょう。

深さ \(D\) の根付き完全 \(K\) 分木があります。
まず深さ \(h\) にある頂点 \(v\) をひとつ選び、そこから親に伸びる辺が存在すればそれを切り、 \(v\) を含まない連結成分があればそれを捨てます。
その後、辺を切っていき \(v\) を含まない連結成分を捨てることを繰り返し、 \(v\) を含む連結成分を \(X\) 頂点にすることが目標です。
目標を達成するために切るべき辺の数の最小値を求めてください。但し、達成不能な場合の答えは \(\infty\) とします。

端的に言うと、適当な頂点 \(v\) を選んで、 \(v\) を一番上の頂点としてその連結成分を \(X\) 頂点にするように解きます。
この問題を全ての頂点 \(v\) について解けば、更に言うと \(0 \le h \le D\) を満たす全ての整数 \(h\) について解いて最小値を取ればこの問題が解けます。

結論から言うと、この問題は以下の手順で解けます。

• 最初の切断によって、深さ \(D-h\) の完全 \(K\) 分木が残ります。
• 残った頂点数が \(X\) 未満なら答えは \(\infty\) です。
• そうでなければ、それ以降は以下の貪欲法で解けばよいです。
  • \(i=D-h-1,D-h-2,\dots,0\) の順に、深さ \(i\) の完全 \(K\) 分木である部分木を消せるだけ消す (消した後に \(X\) 頂点未満になるなら消せないが、そうでない限り消し続ける)。

ここからは、この貪欲法の証明を行います。
以降、深さ \(i\) の完全 \(K\) 分木に含まれる頂点の個数を \(V_i\) と書くことにします。この時、 \(V_i=1+K^1+\dots+K^{i}=\frac{K^{i+1}-1}{K-1}\) です。

段階1: \(V_{D-h}-X\) 頂点を \(V_i\) の最小個数で表す時、貪欲に取っていくことが最適であることを示す

この問題は、「 \(V_0,V_1,\dots,V_{D-h-1}\) 円玉が無限にある時、 \(V_{D-h}-X\) 円を最小何枚で払えるか?」という問題と同じです。
この問題が貪欲法で解ける条件については研究がされており、「コイン 貪欲法」のように検索すると調べることができます。
この記事 から条件を引用すると

硬貨を小さい順に \(a_1,a_2,\dots,a_n\) と並べたとき、全ての \(j\) について \(a_{j+1}=pa_j−q\) なる整数組 \((p,q)\) であって \(0 \le q < a_j\) なるものは一意に定まります。
その \((p,q)\) に対し \(H(q) \le p−1\) が全ての \(j\) について成り立つとき、額面の高い硬貨から使うだけ使う貪欲が成立します。
ただし、 \(H(x)\) は \(x\) 円を支払う場合に貪欲法を用いて求めた最小の硬貨の枚数とします。

今回の問題についてこれを判定します。
\(V_1 = (K+1) \times V_0- 0, H(0)=0 \le (K+1)\) なので \(V_0,V_1\) 間は示されました。
\(j \ge 1\) について、 \(V_{j},V_{j+1}\) 間は \(V_{j+1}=\frac{K^{j+2}-1}{K-1} = (K+1) \times \frac{K^{j+1}-1}{K-1} - \frac{K^{j+1}-K}{K-1}\) と変形でき、 \(p=(K+1),q=\frac{K^{j+1}-K}{K-1}=K \times \frac{K^{j}-1}{K-1}\) です。
\(H(K \times \frac{K^{j}-1}{K-1}) = H(K \times V_{j-1}) = K \le (K+1)-1\) なので、貪欲法が成立することが分かりました。

段階2: 段階1の貪欲法に従うような部分木の消し方が実際に可能であることを示す

消すべき頂点の数が \(K\) 以下であった場合は葉をちぎっていけば良いので自明に可能です。
\(K+1\) 頂点を消す場合は、深さ \(1\) の部分木を \(1\) つ丸ごと消すことになります。その後、 \(K\) 個以内の深さ \(1\) の部分木を使うことで \(K(K+1)\) 頂点までは深さ \(2\) の部分木を \(1\) つ使うことにより貪欲法に従う消し方が可能です。
\(K(K+1)+1 = K^2+K+1\) 頂点を消す場合は、深さ \(2\) の部分木を \(1\) つ丸ごと消すことになります。その後、 \(K\) 個以内の深さ \(2\) の部分木を使うことで \(K(K^2+K+1)\) 頂点までは深さ \(3\) の部分木を \(1\) つ使うことにより貪欲法に従う消し方が可能です。
\(K(K^2+K+1)+1 = K^3+K^2+K+1\) 頂点を消す場合は、深さ \(3\) の部分木を \(1\) つ丸ごと消すことになります。 \(\dots\)

これを続けていくことで、この段階の証明が完成します。

この解法の時間計算量は \(O(D^2)\) であり、 \(D \le 60\) であることを考慮すると \(100\) ケース解いても十分高速です。

この方針は小さいケースでの実験等を経由すると辿りつきやすいですが、証明はやや大変です。 別の方針の解説はこちら

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

long long greedy(long long x,long long k,long long p,vector<long long> &a){
  if(x==0){return 0;}
  if(x<0){return 8e18;}
  long long res=0;
  for(long long i=p;i>=0;i--){
    long long use=(x/a[i]);
    res+=use;
    x-=use*a[i];
  }
  if(x>0){return 8e18;}
  return res;
}

int main(){
  int tc;
  cin >> tc;
  while(tc>0){
    tc--;
    long long d,k,x;
    cin >> d >> k >> x;

    long long res=8e18;
    vector<long long> a(d+1);
    a[0]=1;
    for(long long i=1;i<=d;i++){a[i]=a[i-1]*k+1;}

    for(long long h=d;h>=0;h--){
      long long rem=a[h]-x;
      if(0<=rem){
        long long up=1;
        if(h==d){up=0;}
        res=min(res,up+greedy(rem,k,h-1,a));
      }
    }
    cout << res << "\n";
  }
  return 0;
}