[백준] 18276 : Alergični Aron

https://www.acmicpc.net/problem/18276

문제 분석

 엣지마다 가중치가 존재하는 트리에서 부분트리가 가지는 트리의 엣지수 X 엣지의 가중치 최솟값이 최대가 되는 부분 트리를 구하는 문제이다. 단순히, 모든 부분 트리에 대해서 해당 값을 구하면 부분트리의 개수가 평균적으로 $n^2$에 비례하고 부분 트리 내 모든 노드를 순회해야 하므로($n/2$) 수 틀리면 $n^3$의 복잡도가 나오는 그다지 좋은 접근 방식은 아니다. 

 따라서, 부분 트리의 엣지수를 고정시키거나 엣지의 가중치 최솟값중 하나를 고정시키고 둘의 곱이 최대가 되게 끔 고정되지 않은 값은 그리디 하게 최적으로 접근하도록 두는 방식을 생각해야 한다. 1번째로, 트리의 엣지수를 고정시켜도 같은 트리의 엣지수를 가지는 부분트리는 결국 일일이 구해야하고 트리의 엣지수간의 관계도 미묘하다. 결국은, 위의 브루트 포스로 일일히 접근하는 거랑 다를 게 없다.

 2번째로,  엣지의 가중치 최솟값을 고정시킨 경우를 고려해야 하는데, 이 경우는 최소 가중치의 엣지를 기준으로 해당 가중치보다 높은 엣지로만 확장시키는 경우가 둘의 곱이 최대가 되는 케이스이다. 이쯤 되면 알사람은 알겠지만 MST방식에서 크루스칼 알고리즘과 유사한 방식으로 해결 가능하다.(정확히는 반대가 되는 방식으로) 일단 엣지를 가중치 크기별로 내림차순 정렬을 한 후 가중치가 큰 엣지부터 사용하며 Union-find로 트리의 크기를 늘려가면 된다. 이때 각 엣지를 추가할 때마다 최대가 되는  트리의 엣지수 X 엣지의 가중치 최솟값을 업데이트해주면 된다.

문제 해결 전략

기본적으로 위의 방식을 그대로 구현해 주면 된다. 다만 Union-Find시 단순히 노드 간 병합이 아니라 병합된 집합 내에서  엣지의 수와 엣지의 최소 가중치를 저장하고 병합 시 병합되는 두 트리의 해당값을 통해 병합 후의 값을 저장해 주면 된다.   

1. 엣지를 가중치 순으로 오름차순 정렬
2. 가중치가 큰 엣지부터 Union-Find로 노드 끼리를 병합
2-1. 병합되어 구성된 트리 내에서 엣지의 수와 엣지의 최소 가중치 저장
2-2. 매 엣지 추가시 최대가 되는 트리의 엣지수 X 엣지의 가중치 최소값 업데이트

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


//문제분석
//트리의 부분 트리에서 엣지의 최소값과 엣지의 수가 최대가 되게끔하는 문제
//단순히 모든 부분 트리의 경우를 접근하려하면 부분트리의 수가 굉장히크므로 불가능하다는 것을 직관적으로 인지
//엣지의 수를 고정시키는 경우는 삿실상 브루트 포스나 다름없어 불가능
//반대로, 최소값이 고정되었을때 그 최소값보다 큰 엣지로는 최대한 포함하는게 유리
//즉, 특정값 n을 최소로 가지는 w는 n보다 큰 엣지로만 이루어진 가장 큰 트리의 w와 동일
//MST의 크루스칼처럼(이 경우는 최대 비용부터 접근) 엣지를 정렬 후 가장 큰 비용의 엣지부터 
//순차적으로 트리를 이루며 매순간마다 최대비용을 업데이트
//=====================================================================
//해결전략
//1.엣지를 가중치 순으로 정렬
//2.크루스칼 처럼 유니온 파인드로 트리생성
//2-1. 유니온 파인드로 엣지로 연결된 노드 동일집합으로 설정
//2-2. 서로 합친 후 집합의 w 값 계산 저장 / (k,w_min)의 형태  
//2-3. 최대 w 업데이트
//2-4. 반복
//3.전체 순회후 w 반환
//=====================================================================
//필요자료형
//변수
//pair<int,pair<int,int>> edge_t : edge 자료형 정의
//vector<edge_t> edges : edge의 벡터
//vector<int> parents[N+1] : 부모 저장 // 전역변수 저장
//pair<int,int> alegic_level : 엣지의 수와 최소값으로 알러지 수치 정의
//vector<alegic_level> alegic_levels[N+1] : 각 노드별 알러직 레벨 저장 //전역변수 저장
//int max_alegic_level : 결과값
//함수
//int uninon(int node1, int node2) : 단순 합치는거 외에 알러지 레벨 업데이트
//int find(int node) : 부모 찾기

typedef pair<long long,pair<int,int>> edge_t;
typedef pair<int,long long> alegic_level;

vector<int> parents;
vector<alegic_level> alegic_levels;
int n;
long long max_alegic_level(0);

int find_parent_node(int node) 
{
    if (parents[node]!=node) parents[node]=find_parent_node(parents[node]);
    return parents[node];
}

void union_by_edge(edge_t edge)
{
    int node1 = find_parent_node(edge.second.first);
    int node2 = find_parent_node(edge.second.second);
    long long w=edge.first;

    if (node1==node2) return;

    parents[node2]=node1;
    alegic_levels[node1]=make_pair(alegic_levels[node1].first+alegic_levels[node2].first+1,w);
    max_alegic_level=max(max_alegic_level,alegic_levels[node1].first*alegic_levels[node1].second);
}

int main()
{
    vector<edge_t> edges;
    cin >> n;
    
    for (int i = 0; i < n+1; i++)
    {
        parents.push_back(i);
        alegic_levels.push_back(make_pair(0,0));
    }
    
    for (int i = 0; i < n-1; i++)
    {
        long long u,v,w;
        cin >> u >> v >> w;

        edges.push_back(make_pair(w,make_pair(u,v)));
    }
    sort(edges.begin(),edges.end(),
        [](edge_t edge1, edge_t edge2){
            return edge1.first>edge2.first;
        }
    );
    for(auto edge:edges) union_by_edge(edge);

    cout << max_alegic_level;
}