解法一(dfs)
每两个点连接一条边可以看成是两个数相加.根据题干要求,要代价最小,也就是转换成两个加数且这两个加数要相差小.所以也就是分成x/2和x/2或x/2,x/2+1.
#include<iostream>
using namespace std;
typedef long long ll;
ll dfs(ll n)
{
if(n==1||n==2)return 0;
if(n&1)return dfs(n/2)+dfs(n/2+1)+1;//如果是奇数,那么就会相差1
else return dfs(n/2)*2;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
cout<<dfs(n)<<endl;
}
return 0;
}