초기에 간선이 전부 비활성화되어있는 트리가 하나 주어지고, 간선 활성화/비활성화 쿼리를 $2\times10^5$번 처리한 이후, 각 노드에 대해 한 번이라도 연결되었었던 노드들의 개수를 구하면 되는 문제입니다.

각 간선에 대해서, 양쪽 연결 요소를 A, B라 하고 그 간선이 이전에 활성화됐을 때 ans(A) = ans(B) = C라고 한다면, 이번에 그 간선이 활성화됐을 때 새로운 답은 ans(A) + ans(B) - C임을 관찰할 수 있습니다.

이때, 링크 컷 트리를 사용해주면 쿼리 하나를 $O(\log N)$에 처리할 수 있습니다.

• 코드