容易发现，选择两个偶数对于答案没有任何影响，因此先手必然会优先选择两个奇数合并在一起，而后手必然会优先选择一个奇数和一个偶数在一起，我们举个例子，有一个序列 \(\{1,1,1,1,1,1\}\)，先手先取编号为 \(1,2\) 的两个数，后手再取编号为 \(2,3\) 的两个数，此时第 \(3\) 个数为 \(2\)，因此对答案贡献没有影响，这时先手最优是取编号为 \(4,5\) 的两个数，后手最优是取 \(5,6\) 的两个数，发现了没有，先手和后手的一个周期是 \(3\) 个奇数，因此我们只要分讨一下 \(n \bmod 3 = 0\)，\(n \bmod 3 = 1\)，\(n \bmod 3 = 2\) 的三种情况即可，注意这种方法要特判一下前缀只有一个数的情况。
参考代码：
/*
Tips:
你数组开小了吗？
你MLE了吗？
你觉得是贪心，是不是该想想dp？
一个小时没调出来，是不是该考虑换题？
*/
#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
ll t;
void solve()
{
ll n,sum=0,js=0;
cin>>n;
ll a[n+1];
forl(i,1,n)
{
cin>>a[i];
if(a[i]%2)
js++;
sum+=a[i];
/* if(js==0)
cout<<sum<<" ";
else if(js==1)
cout<<sum-1<<" ";
else if(js==2)
cout<<sum<<" ";
else*/
{
/* if(i==1)
cout<<sum<<" ";
else if(js==3)
cout<<sum-1<<" ";
else if(js%2==0 && js!=2)
cout<<sum-js/2+1<<" ";
else if(js!=1)
cout<<sum-js/2+1<<" ";
else if(js==2)
cout<<sum<<" ";
else
{
if(n==1)
cout<<sum<<" ";
else
cout<<sum-1<<' ';
}*/
if(js%3==0)
cout<<sum-js/3;
else if(js%3==1)
{
if(i==1)
cout<<sum;
else
cout<<sum-js/3-1;
}
else
cout<<sum-js/3;
cout<<" ";
}
}
cout<<endl;
}
int main()
{
IOS;
cin>>t;
while(t--)
solve();
/******************/
/*while(L<q[i].l) */
/* del(a[L++]);*/
/*while(L>q[i].l) */
/* add(a[--L]);*/
/*while(R<q[i].r) */
/* add(a[++R]);*/
/*while(R>q[i].r) */
/* del(a[R--]);*/
/******************/
QwQ;
}
/*
3 5 7 9 4 4
8 7 9 4 4
8 7 12 4
8 10 12
30
6:-2
8:-2
4:-2
2:0
10:-4
*/