本文主要是介绍2.子树的大小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
给定一棵包含n个结点的完全m又，结点按从根到叶、从左到右的顺序依次编号。例如下图是一个拥有 11个结点的完全3叉树。
CR
你需要求出第k个结点对应的子树拥有的结点数量
输入格式
输入包含多组询问。
输入的第一行包含一个整数T，表示询问次数
接下来T行，每行包含三个整数n，m，k，表示一组询电
输出格式
输出T行，每行包含一个整数表示对应询问的答案
import os
import sysT = int(input())for _ in range(T):n,m,k=map(int,input().split())#节点左端点 m*(k-1)+2l=m*(k-1)+2#节点右端点 m*(k-1)+m+1r=m*(k-1)+m+1#总节点数ans=1#当前层的节点数res=1while r<=n: #最后端点不等于n表示未到尽头res=res*m #当前层的节点数l=m*(l-1)+2 #更新下一层的最左边子节点r=m*(r-1)+m+1#计算总节点数ans+=resans+=max(0,n-l+1) #加上最后一层的节点数print(ans)参考代码：
import os
import sysT = int(input())for _ in range(T):# 以k为根节点下的m个子节点为m(k - 1) + 2 ~ m(k - 1) + m + 1n, m, k = map(int, input().split())# 表示以k为根节点下的最左边的子节点l = m * (k - 1) + 2# 表示以k为根节点下的最右边的子节点r = m * (k - 1) + m + 1# 子树的结点总数, 根节点个数为1ans = 1# 记录每一层子结点的数量res = 1# 如果子节点最右子节点小于等于n, 说明没到尽头, 这一层子节点是满的while r <= n:# 当前层子节点数目res = res * m# 更新下一层的最左边子节点l = m * (l - 1) + 2# 更新下一层的最右边子节点r = m * (r - 1) + m + 1ans += resans += max(0, n - l + 1) # 最后一层最右端点就是n, 直接用n-l+1计算出这层的结点数量print(ans)这篇关于2.子树的大小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
