백준13513 트리와 쿼리 4

작성일 | In

문제 링크

  • http://icpc.me/13513

사용 알고리즘

  • 센트로이드 디컴포지션

풀이

centroid tree를 만들어놓고 시작합시다.
트리와 쿼리 5와 비슷한 방식으로 풀 것 입니다.

트리와 쿼리 5는 가장 가까운 점을 찾는 문제이기 때문에 상관이 없지만, 이 문제는 가장 먼 점(지름)을 찾아야 하기 때문에 어떤 centroid로부터 멀리 떨어진 두 점을 찾아야 할 필요가 있고, 더 나아가 두 점은 서로 다른 서브 트리에 있어야 합니다. 같은 서브 트리에서 두 점을 고르면 올바른 거리를 구할 수 없고, 현재 centroid에서 처리하는 경로가 아니기 때문에 서로 다른 서브 트리에서 두 점을 골라야 합니다.

트리와 쿼리 5와는 달리, set을 3개 관리해줄 것 입니다.

1
2
vector<multiset<int>> sub[100001]; //sub[i][j] = i의 j번째 자식을 루트로 하는 서브트리의 정점과 i의 거리
multiset<int> submx[100001], st; //submx[i] = sub[i][j]의 최댓값, st = 각 서브트리 안에서의 정답들

각 서브 트리 안에서의 정답은 아래와 같이 구할 수 있습니다.

1
2
3
4
int subDiameter(int v){ //서브트리 지름 = mx + sndmx(mx와 sndmx는 서로 다른 서브트리에서 유래)
    if(submx[v].size() < 2) return -1;
    return *submx[v].rbegin() + *next(submx[v].rbegin());
}

어떤 정점의 색깔이 변경될 때마다 3개의 set에 들어갈 값들을 잘 관리해주면 답은 *st.rbegin()으로 쉽게 구할 수 있습니다.

구현은 화이팅…