2.子树的大小

问题描述
给定一棵包含n个结点的完全m又，结点按从根到叶、从左到右的顺序依次编号。例如下图是一个拥有 11个结点的完全3叉树。
CR
你需要求出第k个结点对应的子树拥有的结点数量
输入格式
输入包含多组询问。
输入的第一行包含一个整数T，表示询问次数
接下来T行，每行包含三个整数n，m，k，表示一组询电
输出格式
输出T行，每行包含一个整数表示对应询问的答案

 
import os
import sys
 
T = int(input())
 
for _ in range(T):
  n,m,k=map(int,input().split())
  #节点左端点 m*(k-1)+2
  l=m*(k-1)+2
  #节点右端点 m*(k-1)+m+1
  r=m*(k-1)+m+1
  #总节点数
  ans=1
  #当前层的节点数
  res=1
  while r<=n: #最后端点不等于n表示未到尽头
    res=res*m  #当前层的节点数
    l=m*(l-1)+2 #更新下一层的最左边子节点
    r=m*(r-1)+m+1
    #计算总节点数
    ans+=res
  ans+=max(0,n-l+1)  #加上最后一层的节点数
  print(ans)
  

参考代码：

import os
import sys

T = int(input())

for _ in range(T):
  # 以k为根节点下的m个子节点为m(k - 1) + 2 ~ m(k - 1) + m + 1
  n, m, k = map(int, input().split())
  # 表示以k为根节点下的最左边的子节点
  l = m * (k - 1) + 2
  # 表示以k为根节点下的最右边的子节点
  r = m * (k - 1) + m + 1
  # 子树的结点总数, 根节点个数为1
  ans = 1
  # 记录每一层子结点的数量
  res = 1
  # 如果子节点最右子节点小于等于n, 说明没到尽头, 这一层子节点是满的
  while r <= n:
    # 当前层子节点数目
    res = res * m
    # 更新下一层的最左边子节点
    l = m * (l - 1) + 2
    # 更新下一层的最右边子节点
    r = m * (r - 1) + m + 1
    ans += res
  ans += max(0, n - l + 1)  # 最后一层最右端点就是n, 直接用n-l+1计算出这层的结点数量
  print(ans)