yunny.world

https://www.acmicpc.net/problem/24532 24532번: 트리와 XOR 쿼리 1번 노드를 루트로 하며 간선에 가중치가 있는 트리가 주어진다. 모든 노드의 번호는 $1, 2, \cdots{} , N$ 으로 이루어져 있다. 두 노드 $x$, $y$ 에 대하여, $x$에서 $y$로 가는 단순 경로 상의 모든 가 www.acmicpc.net 문제 요약 길지 않으니 직접 문제를 읽어보자. 풀이 하루정도 고민하다가 답 보고 해결했다. 에디토리얼이 정말 잘 되어있다. 생각의 흐름을 요약해보자. 트리에서 어떤 두 정점 u, v의 단순 경로 상의 모든 가중치를 xor한 값을 d(u, v)라 하자. 어떻게 d(u, v)를 빠르게 구할까? 더보기 d(u, v) = d(1, u) ^ d(1, v)를 ..

https://www.acmicpc.net/problem/18240 18240번: 이진 탐색 트리 복원하기 가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다. 가능한 수열이 여러 개라면 아무거나 출력해도 좋다. 가능한 수열이 없다면 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 이진 탐색 트리의 모양이 정해지면, (중위순회의 방문 순서) = (그 노드의 값)으로 해당 노드의 값을 찾을 수 있다. 다만, 이진 탐색 트리를 만들 수 없는 경우가 생기는데, 바로 앞에 깊이 i인 경우가 없는데 깊이 i+1인 경우가 나오는 경우이다. 이 경우를 자세히 살펴보면 아래와 같다. dep[i - 1] < dep[i] / 2 + 1 인 경우에는 깊이 i의 ..