루트 노드가 많은 트리일수록 좋은 트리이다

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

요약

방향 간선과 무방향 간선이 섞인 트리에서 간선 방향을 갱신할 때마다 모든 정점에 도달할 수 있는 정점의 수를 구한다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 구현, 그래프
정답자: 아직 제출이 없습니다

문제

$N$ 개의 노드와 $N-1$ 개의 간선으로 이루어진 그래프가 있다. 노드는 $1$ 번부터 $N$ 번까지 번호가 매겨져 있으며, 각 간선은 방향성을 가지고 있을 수도 있고, 무방향성일 수도 있다. 모든 간선의 방향성을 제거할 경우 이 그래프는 트리가 된다.

어떤 노드에서 다른 모든 노드로 가는 경로가 존재하는 경우 이 노드를 '루트 노드'라고 하자. 이 그래프의 '좋음'은 루트 노드의 수로 정의한다. 이 때, 다음 쿼리들을 수행하자.

$u$ 와 $v$ 를 잇는 간선을 $u \rightarrow v$ 의 방향 간선으로 바꾼다.
$u$ 와 $v$ 를 잇는 간선을 $u \leftarrow v$ 의 방향 간선으로 바꾼다.
$u$ 와 $v$ 를 잇는 간선을 무방향 간선으로 바꾼다.

쿼리의 실행 결과는 그래프에 누적된다.

입력

첫 번째 줄에는 노드의 수 $N$ 이 주어진다.

두 번째 줄부터 $N-1$ 개 줄에 걸쳐 간선들에 대한 정보가 주어진다. 간선의 정보는 공백으로 구분된 세 개의 토큰 $U_i$ , $D_i$ , $V_i$ 로 주어지며, $U_i$ 와 $V_i$ 는 정점 번호를 의미하는 정수이고 $D_i$ 는 방향을 의미하는 문자열로 ->, <-, -- 중 하나이다.

$D_i$ 가 ->라면 $i$ 번째 간선은 $U_i \rightarrow V_i$ 인 방향 간선이다.
$D_i$ 가 <-라면 $i$ 번째 간선은 $U_i \leftarrow V_i$ 인 방향 간선이다.
$D_i$ 가 --라면 $i$ 번째 간선은 $U_i \leftrightarrow V_i$ 인 무방향 간선이다.

다음 줄에는 수행할 쿼리의 수 $Q$ 가 주어진다.

다음 줄부터 $Q$ 개의 줄의 각 줄마다 쿼리가 순서대로 주어진다. $i$ 번째 줄에는 세 개의 토큰 $u_i$ $d_i$ $v_i$ 로 주어지며, $u_i$ 와 $v_i$ 는 정점 번호를 의미하는 정수이고 $d_i$ 는 방향을 의미하는 문자열로 ->, <-, -- 중 하나이다.

$d_i$ 가 ->라면 $i$ 번째 간선을 $u_i \rightarrow v_i$ 인 방향 간선으로 설정한다.
$d_i$ 가 <-라면 $i$ 번째 간선을 $u_i \leftarrow v_i$ 인 방향 간선으로 설정한다.
$d_i$ 가 --라면 $i$ 번째 간선을 $u_i \leftrightarrow v_i$ 인 무방향 간선으로 설정한다.

출력

쿼리를 수행할 때마다 그래프의 '좋음'을 한 줄에 하나씩 출력한다.

제한

$2 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le U_i, V_i \le N$ ( $1 \le i \le N-1$ )
$U_i \ne V_i$ ( $1 \le i \le N-1$ )
$U_i$ 와 $V_i$ 를 모두 무방향 간선으로 이었을 때 만들어지는 그래프는 트리다.
주어진 그래프에 $u_i$ 와 $v_i$ 를 잇는 간선이 존재한다.

예제1

예제 1

입력

5
1 -- 2
2 -> 3
2 <- 4
3 -- 5
5
2 -- 4
2 -> 4
5 -> 3
2 -- 3
3 -- 5

예상 출력