NC246911. 子树的大小
描述
牛牛有一颗包含 个结点的
叉树，这些结点编号为
。
定义一颗 叉树：
1、以结点 0 为根。
2、编号为 结点的
个儿子编号分别为：
。
牛妹有 个询问表示为：
。
输入描述
本题采用多组案例输入，第一行一个整数
代表案例组数。
每组案例中，第一行包含三个空格分隔的整数：。
接下来一行包含个空格分隔的整数代表：
。
保证：单个测试点中所有案例
输出描述
对于每组案例，输出共
示例1
输入:
2 9 3 5 0 8 2 1 3 1 1 1 0
输出:
9 1 3 4 1 1
pypy3 解法, 执行用时: 1480ms, 内存消耗: 29980K, 提交时间: 2022-11-26 10:43:56
def count(p:int,k:int,n:int)->int:
if k==1:
return n-p
ans=0
l,r=p,p
while l<n:
ans+=r-l+1
l,r=l*k+1,min(n-1,r*k+k)
return ans
t=int(input())
for i in range(t):
n,k,m=map(int,input().split())
q=list(map(int,input().split()))
for qq in q:
print(count(qq,k,n))
C++(clang++ 11.0.1) 解法, 执行用时: 1057ms, 内存消耗: 1452K, 提交时间: 2022-12-08 16:13:29
#include<bits/stdc++.h>
using namespace std;
int main() {int T;cin>>T;while(T--){long long n,k,m,q;cin>>n>>k>>m;while(m--){cin>>q;if (k==1){cout<<n-q<<endl;continue;}long long ans=0,l=q,r=q;while(l<n){ans+=r-l+1;l=l*k+1,r=min(r*k+k,n-1);}cout<<ans<<endl;}}return 0;}