BOJ 24914 Split the SSHS

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

24914번: Split the SSHS

 

어떻게 맨 처음에 조각의 수를 셀 수 있을까 고민하다가 조각의 개수가 (각 정점에 연결되어 있는 색의 종류 - 1)을 모두 더한 다음 1을 더해준 값이라는 것을 발견했습니다. 트리 몇 개 그려보고 맞는 거 같아서 짜서 맞았습니다.

 

증명은 다음과 같습니다. 이 문제는 트리 하나가 $k$개의 트리(조각)으로 나누어질 때, $k$를 구하는 문제가 됩니다. 이 때 트리에서 정점의 개수는 간선의 개수보다 항상 하나 많으므로 $k$개의 트리의 전체 정점의 개수와 전체 간선의 개수의 차가 $k$가 됩니다. 전체 정점의 개수는 앞서 말한 각 정점에 연결되어 있는 색의 종류를 통해 구할 수 있습니다. 해당 정점에 $x$개의 색의 종류가 연결되어 있다면 $x$개의 트리에 속해 있다는 뜻이므로 전체 정점의 개수에 $x$를 더해주면 됩니다. 전체 간선의 수는 원래 트리의 간선의 수, 즉 $n-1$이 됩니다. 이를 정리하면 앞서 언급한 식이 됩니다.

 

또한 어떤 정점에서 색의 종류가 하나 사라진다는 것은 해당 노드가 어떤 트리의 정점에서 제외되었다는 뜻이므로 정점의 개수에서 1을 빼고 어떤 정점에서 색의 종류가 하나 늘어난다는 것은 해당 노드가 어떤 트리의 정점에 추가되었다는 뜻이므로 정점의 개수에서 1을 더하면 됩니다.

 

구현은 각 노드에 연결되어 있는 색의 종류와 개수를 map으로 관리한 뒤 색을 지우고 다시 색을 칠할 때 해당 색이 0개가 됐으면 전체 조각 수에서 하나를 빼고 해당 색이 1개가 됐으면 전체 조각 수에서 하나를 더하면 됩니다. 다시 보니 구현을 조금 복잡하게 한 거 같은데 더 깔끔하게 할 수 있을거 같긴 합니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define pii pair<int,int>

using namespace std;

int T, n, m, q, color[200020], cnt[200020];
vector<pii> edge;

int32_t main(void) {
  FastIO;
  T = 1;

  while (T--) {
    cin >> n >> m >> q;

    map<pii, int> m;
    edge.resize(n + 1);

    for (int i = 1; i < n; i++) {
      int u, v, w;
      cin >> u >> v >> w;

      edge[i] = { u, v };

      color[i] = w;
      m[{u, w}]++;
      m[{v, w}]++;

      if (m[{u, w}] == 1) cnt[u]++;
      if (m[{v, w}] == 1) cnt[v]++;
    }

    int piece = 1;
    for (int i = 1; i <= n; i++) piece += cnt[i] - 1;

    while (q--) {
      int p, t;
      cin >> p >> t;

      int w = color[p];
      auto [u, v] = edge[p];

      m[{u, w}]--;
      m[{v, w}]--;

      if (m[{u, w}] == 0) {
        cnt[u]--;
        piece--;
      }
      if (m[{v, w}] == 0) {
        cnt[v]--;
        piece--;
      }

      color[p] = t;

      m[{u, t}]++;
      m[{v, t}]++;

      if (m[{u, t}] == 1) {
        cnt[u]++;
        piece++;
      }
      if (m[{v, t}] == 1) {
        cnt[v]++;
        piece++;
      }

      cout << piece << endl;
    }
  }

  return 0;
}