解法一(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;
}