devbelly

문제 www.acmicpc.net/problem/13309 알고리즘 HLD 풀이 트리에서 두 노드를 잇는 경로가 존재하는지 묻는 문제입니다. 추가적으로 조건에 따라 간선을 끊어주기도 합니다. 트리에서 부모 노드는 유일합니다. 즉 부모 노드로 가는 간선은 유일하므로 모든 간선은 루트를 제외한 모든 노드들로 표현이 가능합니다. HLD를 통해 트리를 일자 형태인 배열로 나타낸 후, 세그먼트 트리를 이용해 구간의 최솟값을 구하면 경로가 존재함을 알 수 있습니다. 최솟값이 1이라면 경로가 존재, 0이라면 끊어져 있는 것입니다. 간선을 끊을 때, 세그먼트 트리에 0 값을 업데이트하면 됩니다. 세그먼트 트리에 접근할 때는 $idx$배열을 통해 접근해야 함을 유의하도록 합시다 코드 #include #define rep..

문제 www.acmicpc.net/problem/13512 알고리즘 HLD 풀이 트리 위에서 두 가지 쿼리를 진행해야 합니다. 첫 번째는 $i$번째 정점의 색을 바꾸는 것. 두 번째는 1번 정점에서부터 $v$정점까지 가는 경로 중 첫 번째로 만나는 검은 정점의 번호를 출력하는 것입니다. 트리에서는 문제를 풀기가 어려우므로 HLD를 이용해서 쭉 펴도록 합시다. 일자 상태로 만들었다면 세그먼트 트리의 사용이 가능해집니다. 세그먼트 트리에서 인덱스가 작을수록 트리 위에서는 루트에 가깝습니다. 이러한 이유 때문에 $query$함수에서 세그먼트 트리 쿼리를 처리할 때, 왼쪽에 검은 정점이 있다면 바로 리턴을 했습니다. 오른쪽에 있는 구간은 왼쪽보다 루트로부터 멀기 때문입니다(처음으로 만나는 검은 정점이 아님). ..

문제 www.acmicpc.net/problem/13510 알고리즘 hld 풀이 트리에서 두 개의 쿼리를 처리해야 합니다. 첫 번째는 $i$번째 간선을 업데이트, 두 번째는 경로 사이의 최댓값을 구하는 문제입니다. 두 번째 쿼리는 이전에도 설명 드린 적이 있습니다. 트리에서 한 정점은 부모로 가는 간선이 유일하므로 간선을 정점으로 표시가 가능합니다. 두 정점과 그 사이를 잇는 엣지가 있다면 자식정점의 번호를 간선처럼 생각하면 됩니다. 간선 문제를 해결했다면 첫 번째 쿼리인 간선을 업데이트 하는 것도 자연스레 해결가능합니다. 문제에서 입력받을 때 $i$번 간선이 무슨 정점들을 나타내는지만 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i..

문제 www.acmicpc.net/problem/1626 알고리즘 hld, mst 풀이 MST 대신 두 번째로 작은 스패닝 트리를 구하는 문제입니다. 접근은 그리디하게 MST에서 가장 큰 간선을 제거하는 것입니다. MST를 만들 때 사용하지 않은 간선들을 검사하며 이 때 간선의 양 끝 정점을 $u, v$라고 합시다. MST를 구성했다면 $u, v$를 잇는 경로는 무조건 존재하게 됩니다. $u, v$를 연결하는 경로에서 가장 큰 간선을 제거하고 현재 사용하지 않은 간선으로 대체하며 풀어나가면 됩니다. 현재 사용하지 않은 간선의 무게와 $u, v$를 잇는 가장 큰 간선의 무게가 같은 경우가 있습니다. 이 경우는 MST가 유일하지 않은 경우입니다. 문제에서는 MST와 second MST를 다른 값으로 구분하고..

문제 www.acmicpc.net/problem/13511 알고리즘 HLD 풀이 첫번째 쿼리는 두 정점 사이의 간선가중치의 합, 두번째 쿼리는 k번째 정점을 구하는 문제입니다. 트리에서는 루트정점을 제외하고는 모든 정점의 부모정점을 유일합니다. 이를 이용하면 트리의 리프노드마다 간선의 가중치를 넣을 수 있습니다. u와 v의 lca를 a라고 가정하겠습니다. k번째 정점을 구하기 위해서는 그 정점이 u와 a사이에 있는지 a와 v사이에 있는지를 일차적으로 확인해야합니다. u와 a사이의 정점의 갯수가 cnt개라고 할 때, $k\leq cnt$ 라면 u로 부터 k번 위로 올라가면 되고 a와 v사이에 k번째 정점이 존재한다면 (전체 정점의 갯수 -k+1)번 위로 올라가면 k번째 정점을 구할 수 있습니다. 코드 #i..