강철 공 달리기

시간 제한4초메모리 제한512 MB

요약

트리의 정점에서 칩을 놓거나 제거하는 쿼리를 처리합니다. 매번 모든 칩을 한 정점에 모으는 데 필요한 최소 이동 횟수를 출력합니다.

난이도: 보통10점 중 7점
유형: 트리, 분할 정복, 이분 탐색
정답자: 아직 제출이 없습니다

문제

정점이 $n$ 개인 트리가 주어진다. 각 정점에는 칩이 하나 있을 수 있다. 처음에는 모든 정점이 비어 있다.

다음 두 종류의 쿼리를 처리해야 한다.

정점에 칩을 놓는다
정점에서 칩을 제거한다

각 쿼리 후에 현재 칩 배치의 span을 출력한다.

span은 모든 칩을 같은 정점으로 모으는 데 필요한 최소 연산 횟수이다. 한 번의 연산으로 칩을 인접한 정점으로 옮길 수 있다. 이 과정에서 한 정점에 칩이 여러 개 있을 수 있다.

이 연산들은 span을 정의하기 위해서만 필요하며, 실제로 수행하지는 않는다.

입력

첫째 줄에 정점의 개수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 이후 $n-1$ 개의 줄에 간선의 양 끝점 $u$ , $v$ ( $1 \le u, v \le n$ )가 한 줄에 하나씩 주어진다. 이 간선들은 트리를 이룬다.

다음 줄에 쿼리의 개수 $q$ ( $1 \le q \le 10^5$ )가 주어진다. 이후 $q$ 개의 줄에 문자 c와 정수 v가 주어진다. 문자 c가 +이면 정점 v에 칩을 놓고, -이면 정점 v의 칩을 제거한다. 칩을 놓는 쿼리에서 v에는 칩이 없고, 제거하는 쿼리에서 v에는 칩이 있다. 매 쿼리 후 트리에는 칩이 적어도 하나 있다.

출력

각 쿼리마다 그 쿼리를 적용한 뒤 트리의 span을 한 줄에 하나의 정수로 출력한다.

예제2

예제 1
입력
```
3
1 2
2 3
4
+ 1
+ 3
+ 2
- 1
```
예상 출력
```
0
2
2
1
```

예제 2

입력

예상 출력