알고리즘 공부방

문제 https://oj.uz/problem/view/JOI13_synchronization 문제 보기 - 동기화 (JOI13_synchronization) :: oj.uz JOI Co., Ltd.는 전 세계에 무려 $N$대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다. 각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 oj.uz 트리에서 처음에는 각 노드가 자기 자신만을 들고 있고, 각 시간마다 ..

https://oj.uz/problems/source/20 1. garden 첫 번째로, 각 정점마다 상태가 2가지가 있다.1. 최솟값 간선으로 갈 수 있다. ( 이 간선을 전에 안 지남 )2. 최솟값 간선으로 갈 수 없어서 두번째 최솟값 간선으로 간다. ( 최솟값 간선을 이미 지남 ) 따라서 노드들의 상태를 위의 1, 2번 상태 2개로 나누어 만들자.0~N-1 : 1번 노드 / N~2N-2 : 2번 노드 이제 각 노드들에서 다른 노드로 상태가 유일하게 정해지니, outdegree = 1인 그래프라고 생각할 수 있고, 이를 통해 Functional Graph 라는 것을 알 수 있다. 이제 마지막으로 원래 문제로 돌아가서 어떤 정점 P로부터 K번 간선을 지나고 얻을 수 있는 경로를 구해주면 된다. 일단 o..

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree Centroid Decomposition 은 트리에서 분할정복을 할 수 있도록 해주는 방법이다. 분할정복은 다음과 같이 생각해볼 수 있다. 어떤 구간 [l, r]을 잡아도 어떠한 가운데 점 k를 잡아서 [l, k], [k+1, r] 로 쪼갤 수 있다. 또한, 분할정복에서 나오는 k들에서 [a, k] 와 같은 구간의 개수는 $O(NlogN)$ 개이다. 단순히 말해, 모든 구간들을 $O(NlogN)$ 개의 구간 2개의 합으로 나타낼 수 있으니 이 $NlogN$ 개를 관리하여 해결한다는 것이다. 트리에서도 Centroid 라는 점은 그 점을 제거하면 나오는 서브트리의 집합..