前言
似乎洛谷上的题解和AT官方都给的 \(O(TD^2)\) 算法？
这里给出乱搞搞出的一种 \(O(TD)\) 算法。
题解
首先发现 \(D\) 虽然没给出固定上界，但显然不超过 \(log_2 10^{18}=60\)。
再接下来可以发现删边等价于先选一颗子树，再删掉这颗子树内部的子树。
先纸上瞎画两下，发现子树内部全保留或全删除一定比有些保留有些删除优。
因此我们先猜测答案一定是非常左偏的，例如这样。
（图中外框深色的即为被选中的）
所以我们可以胡出一种看起来很对的做法：预处理所有深度子树的大小，找到比要求节点数大的最深子树，然后在上面拆。
但是很显然这个结论是不对的那你讲它干嘛
考虑对于这种构造方案的hack，一颗深度是4的满二叉树，选5个点。
选择方案显然并不是选子树，因为到根节点可以少掉整颗树根往上的边，因此先选一条从根到底部的路径，再选子树更优。
因此我们对这两种情况分讨取 \(\min\) 即可。
时间复杂度 \(O(TD)\)，所有的点都可以在 1ms 内通过。
Code
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n,i,j,k,m,t;
LL val[1005];
int main() {
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&m,&n,&k);
LL sum=1;
memset(val,0,sizeof(val));
val[0]=1;
for(i=1;i<=m;i++){
sum*=n;
val[i]=val[i-1]+sum;
}
bool flag=false;
for(i=m;i>=0;i--)
if(k==val[i]){
flag=true;
if(i==m) printf("0\n");
else printf("1\n");
break;
}
if(flag==true) continue;
LL ans=0,tmp=0,num=k;
for(i=m;i>=0;i--)
if(k/val[i]>0){
tmp=i;
break;
}
k--;
if(tmp!=m-1)ans++;
for(i=tmp;i>=0;i--){
LL num1=k/val[i];
k-=num1*1ll*val[i];
ans+=(n-num1-1);
if(k==0){
ans++;
break;
}
else k--;
}
if(num-(m-tmp)<=val[tmp]) tmp--;
if(tmp<0){
printf("%lld\n",ans);
continue;
}
num-=(m-tmp);
LL ans1=(n-1)*(m-tmp-1);
for(i=tmp;i>=0;i--){
LL num1=num/val[i];
num-=num1*1ll*val[i];
ans1+=(n-num1-1);
if(num==0){
ans1++;
break;
}
else num--;
}
printf("%lld\n",min(ans,ans1));
}
return 0;
}