[백준/BOJ] 백준 15669번 : 나무 위의 입자

https://www.acmicpc.net/problem/15669 15669번: 나무 위의 입자 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 트리 모양의 입자가속기와 그 위의 어떤 정점에 놓인 특별한 입자 하나를 표시하고 있다. RB 입자라고 불리는 이 특이한 입자는 안정 www.acmicpc.net 1번 정점이 루트인 트리를 만들고, cache[100001][2]에 해당 정점이 루트인 서브트리에서 깊이가 홀수인 노드의 개수와 깊이가 짝수인 노드의 개수를 저장해 놓고, 도착점이 빨간색일 때 이동하는 간선의 총개수가 짝수개이므로 (짝수 깊이 노드, 짝수 깊이 노드) 또는 (홀수 깊이 노드, 홀수 깊이 노드)의 조합이어야 하고, 도착점이 검은색일 때는 이동하는 간선의 총개수가 홀수개이므로 (..

2022.02.05