题解 | #Branch of Faith#

由完全二叉树的性质可知，树的总深度g(n)，除了最后一层，第i层的节点个数为2的i-1次方，当层数为i时，深度j为i-1,即深度 j的节点个数为2的j次方。

要判断与x号节点深度相同的节点数量，只需要判断x的深度high。

若x不在最后一层，则与x号节点深度相同的节点数量为2的high 次方；

若x在最后一层，则与x号节点深度相同的节点数量为n减去第一层至倒数第二层的所有节点数，即n减去最后一层的第一个数字后加1。 下面是代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int T;
	cin>>T;
	while(T--){
		int n,q;
		cin>>n>>q;
		while(q--){
			int x,high=0,sum=__lg(n),ans;
			cin>>x;
			while(x!=1){
				x/=2;
				high++;
			}
			if(high<sum){
				ans=1LL<<high;
			}
			else ans=n-(1LL<<high)+1;
			cout<<ans<<endl;
		}
	}
}