蓝桥杯2023年第十四届省赛真题-子树的大小

利用完全m叉树的编号特点，依次累加各个非叶节点的子节点树，再加上k结点本身。

#include<stdio.h>
int main(){
	long long n, m, k, t, count, l, r, flag;
	scanf("%lld", &t);
	while(t--){//迭代计算K结点的子节点个数，直至加完该子树的最后一个非叶节点的子节点为止 
		scanf("%lld%lld%lld", &n, &m, &k);
		l = r = k;
		count = flag = 1;//至少含有k结点本身 
		while(flag){
			//最左边子结点的编号；之前的k-1个结点每个都有m个子节点，再加上根节点和k结点本身 
			l = (l - 1) * m + 2; 
			r = r*m + 1;//最右子节点的编号,如果满m个子节点的话 
			if(r > n){
				r = n;//k结点的总子节点树不满m个，则更新 
				flag = 0; //找到了最后的非叶节点，无需继续 
			} 
			if(l <= n) count += r - l + 1;//加上当前结点的子节点 
		}
		printf("%lld\n", count); 
	}
	return 0;
}