분필 도둑 (백준 25428)

안녕하세요. 오늘은 분필도둑이 될거예요.

문제

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

아이디어

최대한 많이 가져갈수록 이득입니다.
그래서 특정개수 x에 대해서 그 이상의 분필을 가진 교실들만 모아서 처리를 합시다.
그런데 이를 매번 다 하면 시간초과가 나므로 x가 최댓값부터 쭉 내려오면서 조금씩 크기를 키워나가면 됩니다.
이때 정답은 x*(그때의 집합들중 크기가 최대)인 값이 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll parent[101010] = { 0 }, mx = 0;
ll find(ll x)
{
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}
void Union(ll x, ll y)
{
    x = find(x); y = find(y);
    parent[x] += parent[y];
    parent[y] = x;
    mx = max(mx, max(-parent[x], -parent[y]));
}
bool same(ll x, ll y)
{
    return find(x) == find(y);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, bunpil[101010] = { 0 }, a, b, ans = 0;
    vector <pair <ll, pair <ll, ll> > > v;

    cin >> N;
    for (i = 1; i <= N; i++) parent[i] = -1;
    for (i = 1; i <= N; i++)
    {
        cin >> bunpil[i];
        ans = max(ans, bunpil[i]); //한개만 선택하는 경우
    }
    for (i = 0; i < N - 1; i++)
    {
        cin >> a >> b;
        v.push_back({ min(bunpil[a],bunpil[b]),{a,b} });
    }
    sort(v.begin(), v.end(), greater<>());

    for (i = 0; i < N - 1; i++)
    {
        if (same(v[i].second.first, v[i].second.second)) continue;
        Union(v[i].second.first, v[i].second.second);
        ans = max(ans, v[i].first * mx);
    }
    cout << ans;
}

감사합니다.