Tree Search

시간 제한1초메모리 제한1024 MB

요약

노드가 10만 개 이하인 이진 트리에서 술래 노드를 찾기 위해 부분 트리 포함 여부 질문을 35번 이하로 던져야 합니다.

난이도: 어려움10점 중 8점
유형: 트리, 이분 탐색, 그리디, 분할 정복
정답자: 아직 제출이 없습니다

문제

You are given a rooted binary tree consisting of $N$ vertices. The vertices are numbered from $1$ to $N$ , the root is the vertex number $1$ . Each of the other vertices has a single parent in the tree. The tree is binary, i.e. each vertex can be a parent of at most two other vertices.

One of the vertices is special. You are trying to guess it. You can ask the questions of the following kind: "Is the special vertex in the subtree of vertex $x$ "? A node $y$ is in the subtree of vertex $x$ if and only if the shortest path between $y$ and $1$ goes through vertex $x$ . Note that vertex $x$ is also in its own subtree.

You are allowed to ask this question at most $35$ times. After that you should report your guess.

제한

$2 ≤ N ≤ 100\\, 000$

예제

이 문제는 공개된 예제가 없습니다.