shake1 BOJ 17306 - 전쟁 중의 삶 (트라이, 완전이진트리) https://www.acmicpc.net/problem/17306 무한완전 이진트리가 주어지고 루트(1)부터 각 정점에 순서대로 번호가 매겨진다. 최대 25e4개의 정짐의 번호(2^50보다 작음)가 주어진다. 정점간의 경로 상에 포함되는 모든 정점의 수를 구하라 각 정점의 번호를 2진수로 나타내면 1에서부터 그 정점까지의 경로를 트라이로 표현할 수 있다. 각 정점마다 1에서부터 경로 상의 최대 정점 수는 50개이므로 트라이의 총 노드의 수는 최대 50n개이다. 트라이의 각 노드 u마다 u를 루트로하는 서브트리에 포함된 정점의 수(term==1인 정점의 수)를 d[u]라고 할 때, d[u]가 1이상 n미만인 경우 u는 경로상에 반드시 포함된다. #include #define FAST ios_base::s.. 2020. 6. 10. 이전 1 다음