ある \(X\) 頂点の連結成分を固定した時、その連結成分を得るために切るべき辺の本数はどのように求められるでしょうか?
実は、切るべき辺の数は連結成分内の頂点の元々の次数の総和を \(d\) とすると \(d-2(X-1)\) と書くことが出来ます。

証明:
当然ながら、 \(X\) 頂点の連結成分は必ず木になります。なので、そこに含まれる辺の数は \(X-1\) 本であり、握手補題より連結成分内の頂点の次数和は \(2(X-1)\) となります。
よって、連結成分内外を結ぶ辺の数は \(d-2(X-1)\) となります。

よって、「切るべき辺の数 \(d-2(X-1)\) を最小化する問題」は「次数和 \(d\) を最小化する問題」に変換されます。

完全 \(K\) 分木の各頂点の次数を調べると

• 根の次数は \(K\)
• 葉の次数は \(1\)
• それ以外の頂点の次数は \(K+1\)

となります。なので、以下の \(2\) 通りの問題を解けばこの問題に正解できます。

• ある \(X\) 頂点の連結成分を選ぶとき、含まれる葉の数を最大化する問題
• ある \(X\) 頂点の連結成分を選ぶとき、 根を必ず使うという条件のもと 、含まれる葉の数を最大化する問題

これらの問題は、「葉を \(L\) 個含むには頂点が最低何個必要か?」を解いて \(L\) を二分探索すれば解くことができます。
「葉を \(L\) 個含むには頂点が最低何個必要か?」は、同じ深さの連結成分を \(K\) 個(以下)まとめて親をつけることを繰り返せば容易に解くことができます。
求めた葉の最大数から次数和を復元し、元の問題の答えを得ることができます。

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

この方針は「次数和」に着目する閃きが必要ですが、証明は容易です。 別の方針の解説はこちら

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}

long long leaf_greedy(long long num,long long d,long long k,bool use_root){
  long long res=0;
  for(long long i=d;i>=0;i--){
    if(use_root){res+=max(1ll,num);}
    else{res+=max(0ll,num);}
    if(num==1){num=0;}
    else{num=llceil(num,k);}
  }
  return res;
}

long long solve(long long d,long long k,long long x,bool use_root){
  long long l=0,r=2e18;
  while(l<=r){
    long long te=(l+r)/2;
    if(leaf_greedy(te,d,k,use_root)<=x){l=te+1;}
    else{r=te-1;}
  }
  long long degsum;
  if(use_root){
    degsum=r+k+(x-r-1)*(k+1);
  }
  else{
    degsum=r+(x-r)*(k+1);
  }
  return (degsum-2*(x-1));
}

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    long long d,k,x;
    cin >> d >> k >> x;
    cout << min(solve(d,k,x,true),solve(d,k,x,false)) << "\n";
  }
  return 0;
}