Given a connected component with \(X\) vertices, how can we find the number of edges to cut required to obtain the connected component?
In fact, \(d-2(X-1)\) needs to be cut, where \(d\) is the sum of original degrees of the vertices within the connected component.

Proof:
Of course, the \(X\)-vertex connected component always forms a tree. Thus, it has \((X-1)\) vertices. By the handshake lemma, the sum of degrees within the connected component is \(2(X-1)\).
Thus, the number of edges connecting inside the outside the connected component is \(d-2(X-1)\).

Therefore, “minimizing the number \(d-2(X-1)\) of edges to cut” is boiled down to “minimizing the sum of degrees \(d\).”

What are the degrees of the vertices in a perfect \(K\)-ary tree? The degree of

• the root is \(K\),
• the leaf is \(1\),
• and the other vertices are \(K+1\).

Thus, we need to inspect the following two cases.

• Choose a connected component with \(X\) vertices to maximize the number of leaves in it.
• Choose a connected component with \(X\) vertices to maximize the number of leaves in it, if the leaf must be used.

These problem can be solved with a binary search on \(L\): “at least how many vertices are needed so that the connected component contains \(L\) vertices?”
This subproblem can be easily solved by repeatedly attaching a parent to (at most) \(K\) connected components with the same depth.
All that left is to restore the degree sum from the obtained maximum number of leaves to find the solution to the original problem.

The time complexity of this solution is \(O(D \log K^D)=O(D^2 \log K)\). Since \(D \le 60\), this is fast enough even with \(100\) cases.

While this solution requires a flash on the degree sum, but the proof is easy. Editorial of another solution

Sample code (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;
}