1. 题目解析

因为 $i$ 和 $i/2$ 在同一个县城时，$i$ 才有贡献 而完全二叉树的节点编号为 $i$ 的节点，父节点为 $i/2$，由此可以想到树形dp

2. 树形dp解释

$f_{x,i,k}$ 表示以 $x$ 为根的子树，根是在 $i$ 县城，有 $k$ 个节点在 $1$ 县城的最大贡献值。

3. 转移方程

因此可以得到转移方程

( $j$ 为左儿子的县城，$l$ 为以左儿子为根子树中1县城的个数，$v$ 为右儿子的县城，$r$ 为以有儿子为根子树中 $1$ 县城的个数)

4. 代码

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int n,a[100005],dp[405][5][405],s[1000005];
void sum(int x) {
	s[x]=1;
	if(x*2<=n)sum(x*2);
	if(x*2+1<=n)sum(x*2+1);
	s[x]+=s[x*2]+s[x*2+1];
}
void dfs(int x) {
	for(int i=1; i<=2; i++) {
		for(int j=0; j<=s[x]; j++) {
			dp[x][i][j]=-1e9-7;
		}
	}
	int ls=2*x,rs=2*x+1;
	if(ls>n) {
		dp[x][1][1]=0;
		dp[x][2][0]=0;
		return;
	}
	if(ls<=n)dfs(ls);
	if(rs<=n)dfs(rs);
	if(rs>n) {
		for(int i=1; i<=2; i++) {
			for(int j=1; j<=2; j++) {
				for(int l=0; l<=s[ls]; l++) {
					if(dp[ls][j][l]<-1e9-7)continue;
					int k=l+(i==1);
					if(k>s[x])continue;
					int d=(i==j?a[ls]:0);
					if(dp[ls][j][l]+d>dp[x][i][k])dp[x][i][k]=dp[ls][j][l]+d;
				}
			}
		}
	} else {
		for(int i=1; i<=2; i++) {
			for(int j=1; j<=2; j++) {
				for(int l=0; l<=s[ls]; l++) {
					if(dp[ls][j][l]<-1e9-7)continue;
					for(int v=1; v<=2; v++) {
						for(int r=0; r<=s[rs]; r++) {
							int k=l+r+(i==1);
							if(k>s[x])continue;
							int d=(i==j?a[ls]:0)+(i==v?a[rs]:0);
							if(dp[ls][j][l]+dp[rs][v][r]+d>dp[x][i][k])dp[x][i][k]=dp[ls][j][l]+dp[rs][v][r]+d;
						}
					}
				}
			}
		}
	}
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++)cin>>a[i];
	sum(1);
	dfs(1);
	cout<<max(dp[1][1][n/2],dp[1][2][n/2])<<endl;
	return 0;
}