MathTrauma

문제 링크 : https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 최소 공통 조상을 \(\log(n)\) 시간 이내로 찾을 수 있도록 해주는 것은 이중 배열 prv 이다. 이 배열은 음이 아닌 정수 k 에 대해 \(2^k\) 만큼 앞의 선조에 대한 정보를 기록하고 있다. prv[i][k] 는 i 번 노드의 \(2^k\) 번째 선조로 prv[i][k]=prv[prv[i][k-1]][k-1] 을 만족한다. 도..

문제 링크 : https://www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net persistent segment tree + lca 로 해결했다. (더 나은 방법은 없을까?) lca 를 위한 dfs 를 거치면서 부모 노드가 각 자식노드를 생성하는 segment tree 이다. 최소공통조상(lca)는 아래 글에서 간략히 정리해 두었으니 참조. BOJ 3584 Nearest Common Ancestors BOJ 3584 Nearest..