BOJ 15756 - Disruption

BOJ 15756 - Disruption

어떤 간선에 대해서 끊어졌을 때 상황을 생각하지 말고, 모든 이을 수 있는 간선들을 기준으로 생각하자.

어떤 간선 $u-v$ 를 이을 수 있다면 정확히 $u \leftrightarrow v$ 로 가는 경로에 있는 모든 간선만 하나가 끊어져도 이 간선을 이용해 이어줄 수 있다는 것이다.

따라서 추가해줄 수 있는 간선을 $c$ 에 대해 내림차순 정렬하고 $HLD$ 같은 편리한 걸 이용해 $u-v$ 구간에 있는 모든 간선들에 대해서 값을 업데이트해주면 된다.

정해는 HLD나 LCA도 안쓰고 단순히 disjoint set을 계속 앞뒤로 연결시켜주며 경로를 압축하는 테크닉을 사용하여 $O(m)$에 풀 수 있다고 한다.

const int inf = 2e9;
void solve() {
   int n, m;
   cin >> n >> m;
   HLD<int> hld(n);
   vector<pi> e;
   for (int i = 0, u, v; i < n - 1; i++) {
      cin >> u >> v, u--, v--;
      e.pb({u, v});
      hld.add_edge(u, v, inf);
      hld.add_edge(v, u, inf);
   }
   hld.init();
   vector<array<int, 3>> edges;
   for (int i = 0, u, v, c; i < m; i++) {
      cin >> u >> v >> c, u--, v--;
      edges.pb({c, u, v});
   }
   sort(all(edges), greater<>());
   for (auto &[c, u, v]: edges) {
      hld.update_path(u, v, c);
   }
   for (auto &[u, v]: e) {
      if (hld.depth[u] < hld.depth[v]) swap(u, v);
      int ret = hld.query_sum(u, v);
      if(ret == inf) cout << -1 << endl;
      else cout << ret << endl;
   }
}