AcWing 1240. 完全二叉树的权值 (简单暴力DFS)
原题链接
简单
作者:
纸染
,
2021-04-14 11:16:17
,
所有人可见
,
阅读 417
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n;
ll tree[N], sum[N];
int d;
void dfs(int u, int depth) {
if (u > n) return ;
d = max(d, depth);
sum[depth] += tree[u];
dfs(u << 1, depth + 1);
dfs(u << 1|1, depth + 1);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &tree[i]);
dfs(1, 1);
int mx = 1;
for (int i = 1; i <= d; i++)
if (sum[i] > sum[mx])
mx = i;
printf("%d\n", mx);
return 0;
}