BOJ 25428 - 분필 도둑

BOJ 25428 - 분필 도둑

최근에 USACO에서 푼것같은 문제

어떤 정점 $u$가 현재 $a_u$가 가장 작고 그룹에 포함된다고 하자.

그럼 그 정점 $u$와 연결된 연결그래프에서의 임의의 정점 $v$는 모두 $a_v \ge a_u$ 여야 하므로 연결그래프의 크기 * $a_u$ 가 정답의 후보이다.

이렇게 $a_i$ 가 작은 $i$부터 검사해가며 연결 그래프에서 연결을 끊어주는 것을 반대로해서 $a_i$가 큰것부터 연결그래프를 구성해나가며 Disjoint Set으로 합쳐주며 정답을 구할 수 있다.

특정 시점에서 $u$ 를 포함했다면 정답은 $a_u \times$ 연결 그래프의 크기 로 특정지을 수 있다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n;
   cin >> n;
   vi a(n);
   vvi edges(n);
   fv(a);
   DSU dsu(n);
   for (int i = 0, u, v; i < n - 1; i++) cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);
   vi idx(n);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) { return a[i] > a[j]; });
   ll ans = maxe(a);
   debug(a);
   debug(idx);
   for (int i = 0; i < n;) {
      int j = i;
      while (j < n && a[idx[j]] == a[idx[i]])j++;

      for (int k = i; k < j; k++) {
         for (int to: edges[idx[k]])
            if (a[to] >= a[idx[k]]) {
               dsu.merge(to, idx[k]);
               ans = max(ans, 1ll * dsu.size(idx[k]) * a[idx[i]]);
            }
      }

      i = j;
   }
   cout << ans;
}