백준 12746 (C++) Traffic (Large)

최초 업로드: 2025-09-20 12:23:20

최근 수정 시간: 2025-09-20 12:23:20

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Traffic (Large)

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

## 문제 설명

CINERIS라는 도시국가가 있다. 이 도시국가에는 N개의 철도역이 있고, 역들은 트리 구조로 이어져 있다. 이 도시국가를 통치하는 정민이는 최근에 사람들이 가장 많이 다니는 구간이 어디인지 궁금했다. 지금까지 총 Q개의 표가 팔렸고, 정민이가 각 Q개의 표에서 알아낼 수 있는 정보는 출발역과 도착역의 정보뿐이다.

CINERIS에 살고 있는 사람들은 정민이처럼 모두 똑똑하기 때문에, 최단 거리로 이동했다고 가정한다. 그렇다면, 이 Q개의 정보를 이용하여 사람들이 가장 많이 다니는 구간을 구하여라.

## 입력

첫 번째 줄에 N, Q가 주어진다.

두 번째 줄부터 N번째 줄까지 각 줄에 두 개의 수 a, b가 주어지는데, 이는 a번 역에서 b번 역으로 가는 양방향 철로가 존재함을 의미한다.

N + 1번째 줄부터 N + Q번째 줄까지는 각 표의 출발역과 도착역의 정보 c, d가 주어진다. 이는 표가 c번 역에서 출발하여 d번 역에 도착하였다는 정보를 가짐을 의미한다.

N, Q의 제한은 다음과 같다:

1 ≤ N ≤ 222222, 1 ≤ Q ≤ 222222

## 출력

사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하는 구간(철로)임을 의미하고, 그 구간을 지난 사람의 수가 c명이라는 의미이다. 만약 조건을 만족하는 답인 (a, b) 쌍이 여러 개라면, 사전 순으로 가장 작은것을 출력한다.

## 풀이
HLD 해주고, 분리 집합으로 최댓값 철로들을 전부 다 이어서 그중 사전순으로 가장 앞서는 것을 출력해주었습니다.

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

const int MAX = 222'222;

int subTreeCnt[MAX];
vector<vector<int>> conn(MAX), child(MAX);

int nodeCnt, nodeInverseNum[MAX], nodeNum[MAX], groupCnt, groupNum[MAX], head[MAX], parent[MAX], depth[MAX];

int _size=1, arr[MAX*4], lazy[MAX*4];

int parentForDSU[MAX];

int _find(int x) {
    if(x==parentForDSU[x]) return x;
    return parentForDSU[x] = _find(parentForDSU[x]);
}

void _union(int x, int y) {
    x = parentForDSU[x];
    y = parentForDSU[y];
    if(x>y) parentForDSU[x]=y;
    else parentForDSU[y]=x;
}

int dfs1(int cur) {
 subTreeCnt[cur]=1;
 for(int next:conn[cur]) {
 if(!subTreeCnt[next]) {
 subTreeCnt[cur] += dfs1(next);
 child[cur].push_back(next);
 if(subTreeCnt[child[cur].front()] < subTreeCnt[child[cur].back()]) swap(child[cur].front(), child[cur].back());
 }
 }
 return subTreeCnt[cur];
}

void dfs2(int cur, int curDepth) {
    int u = nodeNum[cur] = nodeCnt++;
    nodeInverseNum[u] = cur;
    depth[u] = curDepth;

groupNum[u] = groupCnt;
    if(head[groupCnt]==-1) head[groupCnt]=u;

if(child[cur].empty()) {
        groupCnt++;
        return;
    }

for(int next:child[cur]) {
        dfs2(next, curDepth+1);
        parent[nodeNum[next]] = u;
    }
}

void updateLazy(int nodeNum) {
 if(lazy[nodeNum]) {
 if(nodeNum<_size/2) {
 lazy[nodeNum*2] += lazy[nodeNum];
 lazy[nodeNum*2+1] += lazy[nodeNum];
 } else {
 arr[nodeNum] += lazy[nodeNum];
 }
 }
}

void updateRange(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 if(R<nodeL || nodeR<L) return;
 if(L<=nodeL && nodeR<=R) {
 lazy[nodeNum]++;
 } else {
 int mid = (nodeL+nodeR)/2;
 updateRange(L, R, nodeNum*2, nodeL, mid);
 updateRange(L, R, nodeNum*2+1, mid+1, nodeR);
 }
}

void query(int u, int v) {
    u = nodeNum[u-1];
    v = nodeNum[v-1];
    while(groupNum[u]!=groupNum[v]) {
        int uHead = head[groupNum[u]], vHead = head[groupNum[v]];
        if(depth[uHead]>depth[vHead]) {
            updateRange(uHead, u);
            u = parent[uHead];
        } else {
            updateRange(vHead, v);
            v = parent[vHead];
        }
    }
    updateRange(min(u, v)+1, max(u, v));
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, q; cin >> n >> q;
 for(int i=0;i<n-1;i++) {
 int u, v; cin >> u >> v;
 conn[u-1].push_back(v-1);
 conn[v-1].push_back(u-1);
 }
 dfs1(0);
 memset(head, -1, sizeof head);
 dfs2(0, 0);

while(_size<n) _size<<=1;
 _size<<=1;

while(q--) {
        int u, v; cin >> u >> v;
        query(u, v);
    }

int c=0;
 for(int i=1;i<_size/2+n;i++) {
 updateLazy(i);
 if(i>=_size/2) c = max(arr[i], c);
 }

for(int i=0;i<n;i++) parentForDSU[i]=i;
 for(int i=_size/2;i<_size/2+n;i++) {
 if(c==arr[i]) _union(nodeInverseNum[i-_size/2], nodeInverseNum[parent[i-_size/2]]);
 }

for(int i=0;i<n;i++) {
 if(parentForDSU[i]!=i) {
 cout << parentForDSU[i]+1 << ' ' << i+1 << ' ' << c;
 return 0;
 }
 }
}
```