CHOICE

오일러 투어로 각 정점 $x$의 서브트리를 구간 $[in_x,out_x]$에 대응시킨다.

우현이의 현재 위치를 $u$라 할 때, 각 정점 $v$에 대해 $d(v)=\mathrm{dist}(u,v)$를 유지한다. 우현이가 $u$에서 인접한 로 움직이고 간선의 길이가 라면, 두 정점을 연결하는 간선을 제거했을 때 쪽 컴포넌트의 정점까지의 거리는 감소하고, 나머지 정점까지의 거리는 증가한다.

특히 $x$가 $u$의 자식이면 모든 정점의 거리에 $w$를 더한 후 $x$의 서브트리의 거리에 $2w$를 뺀다. 반대로 $x$가 $u$의 부모이면 모든 정점의 거리에서 를 뺀 후 의 서브트리의 거리에 를 더한다.

세그먼트 트리의 각 구간에서 선택된 정점과 선택받지 못한 정점까지의 거리 최솟값을 따로 저장한다. 구간 거리 덧셈은 두 최솟값 모두에 적용하고, 구간 상태 반전은 두 최솟값을 교환한다. 두 연산은 지연 전파로 처리할 수 있다. $3$번 쿼리의 답은 세그먼트 트리 루트가 저장하는 선택된 정점까지의 거리 최솟값이며, 선택된 정점이 없으면 $-1$이다.

전처리는 $O(N)$, 각 쿼리는 $O(\log N)$ 시간이고, 메모리는 $O(N)$이다. 가중치 합과 구간 덧셈은 long long으로 처리한다.