BOJ 31740 Split the SSHS 3

📝 문제 정보

링크: https://www.acmicpc.net/problem/31740

🧐 관찰 및 접근

문제에서 주어진 그래프는 트리로 보인다.
- 트리에서는 모든 간선이 단절선이므로 하나만 잘라도 두 컴포넌트로 나뉘는것이 자명하다.
- 간선을 하나 자르고 나면 서브트리 하나와 나머지 부분으로 나뉜다.
  - 서브트리의 가중치는 트리DP를 활용해 미리 계산해둘 수 있고, 나머지 부분은 전체 가중치 합에서 해당 서브트리의 가중치 합만큼을 빼면 된다.
  - $O(N)$에 계산 가능해보인다.

💻 풀이

코드 (C++):

int dfs(int c, int p){
    par[c] = p;
    DP[c] = W[c];
    for(auto nxt : links[c]){
        if(nxt == p) continue;
        DP[c] += dfs(nxt, c);
    }
    return DP[c];
}

void solve(){
    cin >> N;
    rep(i, 0, N-1){
        int u, v; cin >> u >> v;
        links[u].push_back(v);
        links[v].push_back(u);
    }
    rep(i, 1, N+1) cin >> W[i];

    int SUM = dfs(1, -1);
    int ans = 2e9;
    pii ans2 = {-1, -1};
    rep(i, 2, N+1) if(ans > abs(DP[i] - (SUM - DP[i]))){
        ans = abs(DP[i] - (SUM - DP[i]));
        ans2 = {i, par[i]};
    }
    cout << ans << '\n';
    cout << ans2.first << ' ' << ans2.second << '\n';
}