ACM ICPC 인터넷 예선 A번

1) root에서 leaf node까지의 최장 경로를 구한다.
2) 그 최장 경로값을 루트에서 리프까지의 거리로 지정하고
3) 상위 노드에 연결된 간선부터 최대한 증가시켜준다.

구현)
1)


code)
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

void dfs(int, int);
void dfs2(int, int);

vector<vector<pair<int, int> > > adj(2500000);
int maxDist[2500000]={0, };
int ans=0;
int main() {
    int k;
    scanf("%d", &k);
    //root : 1
    for(int i=1; i<(1<<k); i++) {
        for(int j=0; j<2; j++) {
            int cost;
            scanf("%d", &cost);
            adj[i].push_back(make_pair(2*i+j, cost));
            ans+=cost;
        }
    }
   
    dfs(1, -1);
    dfs2(1, -1);
    printf("%d\n", ans);
    return 0;
}

void dfs2(int node, int p) {
    for(int i=0; i<adj[node].size(); i++) {
        int child=adj[node][i].first;
        if(child==p) continue;
        int cost=adj[node][i].second;

        dfs2(child, node);
        int add=(maxDist[node]-maxDist[child])-cost;
        adj[node][i].second+=add;
        ans+=add;
    }
}

void dfs(int node, int p) {
    maxDist[node]=0;
    for(int i=0; i<adj[node].size(); i++) {
        int child=adj[node][i].first;
        if(child==p) continue;
        int cost=adj[node][i].second;

        dfs(child, node);
        maxDist[node]=max(maxDist[node], maxDist[child]+cost);
    }
}