백준 34735 (C++) Dangerous City

최초 업로드: 2025-11-15 06:34:29

최근 수정 시간: 2025-11-15 06:34:29

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] Dangerous City

[문제 링크](https://www.acmicpc.net/problem/34735)

## 문제 설명

Alice is moving to the city of Nlogonia, and to decide where to live, she is evaluating the safety of the city.

Nlogonia is a planned city with $N$ intersections, numbered from $1$ to $N$, and $M$ streets. Each street connects two intersections bidirectionally. It is guaranteed that any intersection can reach all other intersections using the streets, and no two streets connect the same pair of intersections.

The government of Nlogonia publishes a danger rating $D_i$ for each intersection $i$. However, Alice thinks these ratings are insufficient because she wants to assess the safety of moving through the city, not just where she lives. So, she developed her own way to measure how dangerous the city is.

For any given path in the city, Alice defines its path risk as the maximum danger rating among all intersections on that path, including its endpoints. The risk factor between two intersections $U$ and $V$, denoted as $f(U, V )$, is the minimum possible path risk among all paths connecting $U$ and $V$. By definition, the only path from an intersection $U$ to itself is the trivial path containing only $U$, so we have $f(U, U) = D_U$. Finally, she assigns a danger score to each intersection $U$, denoted as:

$$S_U = \displaystyle\sum_{V=1}^{N}{f(U,V)}$$

In other words, the danger score of an intersection $U$ is the sum of its risk factors to every intersection in the city.

Computing these danger scores for all intersections is not easy, so Alice asks for your help!

## 입력

The first line contains two integers $N$ ($2 ≤ N ≤ 3 \cdot 10^5$) and $M$ ($1 ≤ M ≤ 3 \cdot 10^5$), indicating respectively the number of intersections and streets in Nlogonia. Each intersection is identified by a distinct integer from $1$ to $N$.

The second line contains $N$ integers $D_1, D_2, \dots , D_N$ ($1 ≤ D_i ≤ 10^9$ for $i = 1, 2, \dots , N$), where $D_i$ is the danger rating of intersection $i$.

Each of the next $M$ lines contains two integers $U$ and $V$ ($1 ≤ U, V ≤ N$ and $U \ne V$), indicating that there is a two-way street between intersections $U$ and $V$.

It is guaranteed that there is at most one street between each pair of intersections and that any intersection can be reached from any other using one or more streets.

## 출력

Output a single line with $N$ integers $S_1, S_2, \dots , S_N$, that is, the danger scores of all the intersections.

## 풀이
최종적으로 모든 노드를 연결시키면 MST가 된다. cost가 낮은 노드부터 넣으면서 간선을 연결시켜 MST를 완성시키면 된다. 이 과정에서 각 노드를 넣으면서 연결되는 노드를 자식으로 삼으면 트리로 만들 수 있다.

이때 한 노드에 추가되는 cost는 부모 노드에는 부모의 서브 노드 수 * 부모의 가중치가 더해지고, 각 자식 노드들에는 (부모의 서브 노드 수 - 각 자식의 서브 노드 수) * 부모의 가중치가 더해진다. 이를 트리DP로 해결할 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 300'000;

ll parent[MAX], _size[MAX], w[MAX], res[MAX], dp[MAX];
vector<vector<int>> conn(MAX), child(MAX);

int find(int x) {
    if(parent[x]==x) return x;
    return parent[x] = find(parent[x]);
}

void dfs(int curConned) {
    for(int next:child[curConned]) {
        dp[next] += dp[curConned];
        dfs(next);
    }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=0;i<n;i++) cin >> w[i];
 while(m--) {
 int u, v; cin >> u >> v;
 conn[u-1].push_back(v-1);
 conn[v-1].push_back(u-1);
 }

vector<int> node(n);
 for(int i=0;i<n;i++) {
 node[i]=parent[i]=i;
 _size[i]=1;
 }
 sort(node.begin(), node.end(), [](int a, int b){return w[a]<w[b];});

int root=0;
 unordered_set<int> inTree;
 for(int e:node) {
 ll sum=1;
 bool chk=true;
 unordered_set<int> curConned;
 for(int next:conn[e]) {
 next = find(next);
 if(find(e)==next) {
 chk=false;
 break;
 }
 if(inTree.count(next) && !curConned.count(next)) {
 sum += _size[next];
 curConned.insert(next);
 }
 }
 if(!chk) continue;

res[e] += sum*w[e];
 for(int next:curConned) {
 dp[next] += (sum-_size[next])*w[e];
 parent[next]=e;
 _size[e] += _size[next];
 child[e].push_back(next);
 }
 inTree.insert(e);
 root=e;
 }
 dfs(root);
 for(int i=0;i<n;i++) cout << res[i]+dp[i] << ' ';
}
```