Binary Tree Queries

어떤 정점 $v$를 루트로 정하면, $v$의 모든 이웃은 $v$의 자식이 된다. 따라서 차수가 $3$ 이상인 정점을 루트로 정하면 이진 트리가 될 수 없다.

어떤 정점을 루트로 정해도 이진 트리라는 조건으로부터 모든 정점의 차수는 $2$ 이하이다. 연결된 트리에서 모든 정점의 차수가 $2$ 이하이면 트리는 하나의 경로이다.

경로의 한쪽 끝점부터 정점을 순서대로 나열한다. 정점 $v$의 위치를 $P_v$라 하자. 현재 루트의 위치를 $R$, 쿼리에서 주어진 정점 $i$의 위치를 $P$라 하자.

흰색 정점의 개수를 관리하는 Fenwick tree를 경로 순서 위에 만든다. $S(x)$를 경로의 첫 번째 정점부터 $x$번째 정점까지의 흰색 정점 수라고 하자.

$P<R$이면 현재 루트는 $i$의 오른쪽에 있다. 따라서 $i$의 서브트리는 구간 $[1,P]$이고, $i$부터 루트까지의 경로는 구간 이다.

$$a=S(P),\qquad b=S(R)-S(P-1)$$

$P>R$이면 현재 루트는 $i$의 왼쪽에 있다. 따라서 $i$의 서브트리는 구간 $[P,N]$이고, $i$부터 루트까지의 경로는 구간 이다.

$$a=S(N)-S(P-1),\qquad b=S(P)-S(R-1)$$

$P=R$이면 $i$가 현재 루트이다. 이때 서브트리는 전체 트리이고, 경로에는 $i$만 포함된다.

$$a=S(N),\qquad b=C_i$$

1번 쿼리는 현재 루트의 위치만 바꾸면 된다. 2번 쿼리는 Fenwick tree의 한 위치에 $1$ 또는 $-1$을 더한다. 3번 쿼리는 위 식을 이용해 구간 합을 계산한다.

경로 순서를 구하는 데 $O(N)$, Fenwick tree를 만드는 데 $O(N\log N)$이 걸린다. 각 쿼리는 $O(\log N)$에 처리되므로 전체 시간 복잡도는 $O((N+Q)$이고, 공간 복잡도는 이다.

Solution written by GPT5.6