백준 26159 - 트리와 수열 (C++)

문제

• 문제 링크

  
   BOJ 26159 - 트리와 수열 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리와 $N - 1$개의 수열이 주어진다.
간선에 수열의 원소들을 하나씩 대응시켜 가중치를 매길 때, $min(Σdist(i, j))$ $mod$ $1000000007$ 의 값을 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$2 ≤ N ≤ 100,000$

$1 ≤ a_i ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 트리(trees)
• 다이나믹 프로그래밍(dp)
• 트리에서의 다이나믹 프로그래밍(dp_tree)
• 그리디 알고리즘(greedy)
• 정렬(sorting)

풀이

척 보면 드는 생각이, "가장 인기 없는 간선일수록 큰 가중치를 부여 하는 것이 이득이지 않을까?" 였다.
많이 이용되는 간선일수록 최대한 적은 가중치를 메기는 것이 최선일테니 말이다.

이를 위해선 존재하는 모든 $(i, j)$쌍에 대해 각 간선마다 이용되는 횟수를 계산해야 한다.

구체적으로 $dp[i] :$ " 정점 $i$와 $i$의 부모를 잇는 간선이 이용되는 횟수" 라고 할 때,

$($정점 $i$를 루트로 하는 서브 트리의 크기$)$ $*$ $($이에 속하지 않는 나머지 모든 정점$)$ 의 형태로 구할 수 있다.

---

이제 수열 $a[]$ 와 $dp[]$ 가 서로 다른 성격(단조 증가 / 감소)을 갖도록 정렬하면 $Σdist(i, j)$ $mod$ $1000000007$ 의 최솟값을 계산할 수 있다.

증명은 여기 에서 간단하게 확인할 수 있다.

자세한 흐름은 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <int> Gr[N];
long long dp[N];
int n, a[N];
 
int SubSize(int p)
{
    dp[p] = 1;
    for (int i : Gr[p])
        if (!dp[i])
            dp[p] += SubSize(i);
    return dp[p];
}
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i, j, o{}; ++o < n;)
        cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
    for (int i(1); i < n; cin >> a[i++]);
}
void Solve(int r = 0)
{
    SubSize(1);
    sort(a, a + n);
    for (int i(1); i <= n; i++) dp[i] *= (n - dp[i]);
    sort(dp + 1, dp + n + 1, greater<>());
 
    for (int i(1); i < n; i++)
        r = (r + dp[i] * a[i]) % 1000000007;
    cout << r;
}
int main()
{
    Init();
    Solve();
}

comment

끝