CFR 526 B. Om Nom and Dark Park ( Greedy )

Problem - B - Codeforces
Since it is always better to put lamps on an edge nearer to the root, rather than putting the same quantity on both brother edges, we will maintain the subtrees along backtracking DFS, such that when considering a subtree, its subtrees have already been solved.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 1;
const int MAX2N = ( 1 << MAXN ) + 2;

int n;
int fa_cost[ MAX2N ];

int lamp[ MAX2N ];

void upmax(int &x, int v){
    if( x < v ) x = v;
}

int dfs1(int u, int d){
    if( d == n ) return lamp[ u ] = 0;
    upmax( lamp[ u ], dfs1( u << 1, d + 1 ) + fa_cost[ u << 1 ] );
    upmax( lamp[ u ], dfs1( u << 1 | 1, d + 1 ) + fa_cost[ u << 1 | 1 ] );
    return lamp[ u ];
}

int ans;
void dfs2(int u, int d){
    if( d == n ) return;
    dfs2( u << 1, d + 1 );
    dfs2( u << 1 | 1, d + 1 );
    if( fa_cost[ u << 1 ] + lamp[ u << 1 ] < fa_cost[ u << 1 | 1 ] + lamp[ u << 1 | 1 ] ){
        swap( fa_cost[ u << 1 ], fa_cost[ u << 1 | 1 ] );
        swap( lamp[ u << 1 ], lamp[ u << 1 | 1 ] );
    }
    ans += fa_cost[ u << 1 ] + lamp[ u << 1 ];
    ans -= fa_cost[ u << 1 | 1 ] + lamp[ u << 1 | 1 ];
    fa_cost[ u << 1 | 1 ] = fa_cost[ u << 1 ] + lamp[ u << 1 ] - lamp[ u << 1 | 1 ];
}

void solve(){
    dfs1( 1, 0 );
    dfs2( 1, 0 );
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 2; i < ( 1 << n + 1 ); ++i)
        scanf("%d", &fa_cost[ i ]);
    solve();
    return 0;
}