AP 위의 수업은?

AP 위의 수업은? 온라인 수업

MatKor의 규모가 점점 커지면서, MatKor 세미나도 온라인으로 진행하고자 한다. 민재는 세미나를 위해 네트워크를 설계했다. 네트워크는 $N$명의 부원이 각자 한 개의 정점에 위치하고, 정점들 사이의 무방향 간선으로 통신할 수 있는 트리(사이클이 없는 연결 그래프) 형태이다. 편의상 모든 정점들의 집합을 $V$, 모든 간선들의 집합을 $E$라고 하자. 간선들은 해당 간선을 사용하기 위한 비용이 있는데, 간선 $e$의 비용을 $w\_e$로 정의한다.

$N$명의 부원과 $N$개의 노드는 각각 $1$번부터 $N$번까지 번호가 매겨져 있으며, $i$번 부원은 $i$번 노드에 위치한다. 초기에 $M$명이 세미나를 신청했으며, 이 부원들이 위치한 정점들의 집합을 $S\left( \subseteq V \right)$라고 하자.

두 정점 $u,v$에 대해 $E\_{u,v}$는 $u$와 $v$ 사이 경로의 간선들의 집합을 의미하며, $d\_{u,v}$는 $u$와 $v$ 사이 경로의 비용의 합 즉, $\sum\_{e\in E\_{u,v}}w\_e$을 의미한다. 이때 $u=v$라면 $E\_{u,v}=\varnothing$이며, $d\_{u,v}=0$이다.

이제 민재는 $N$개의 정점 중 한 곳에서 세미나를 송출할 것인데, 세미나를 듣는 모든 부원까지 도달하기까지 총 비용이 얼마나 되는지를 알고 싶다. 이때 중복되는 간선에 대해 중복되는 횟수만큼 비용을 더하는 경우와 한 번만 더하는 경우 모두 알고 싶다. 중복되는 횟수만큼 비용을 더하는 경우를 트래픽합, 한 번만 더하는 경우를 하드웨어합이라 정의힌다. 세미나를 진행하는 도중 신청하지 않았던 인원이 새로 신청할 수도, 신청했던 인원이 신청을 취소할 수도 있으므로 이를 실시간으로 반영하여 계산해야 한다.

민재는 이를 해결하기 위해 다음 세 종류의 쿼리를 수행하는 프로그램을 작성하면 된다는 사실을 알았다.

• 1 $v$ : $v$번 부원이 세미나 신청 여부를 반전시킨다. 즉, $v\in S$라면 S\leftarrow S\setminus\left\\{ v \right\\}를, $v\notin S$라면 S\leftarrow S\cup\left\\{ v \right\\}를 $S$에 반영한다.
• 2 $v$ : $v$번 부원이 위치한 정점에서 세미나를 송출했을 때 트래픽합을 출력한다. 즉, $\sum\_{s\in S}d\_{s,v}$를 출력한다.
• 3 $v$ : $v$번 부원이 위치한 정점에서 세미나를 송출했을 때 하드웨어합을 출력한다. 즉, $E\_v\left( S \right) =\bigcup\_{s\in S}E\_{s,v}$이라 할 때, $\sum\_{e\in E\_v\left( S \right)}w\_e$를 출력한다.

위의 세 종류의 쿼리를 수행하는 프로그램을 작성해 보자.

첫 번째 줄에 부원의 수 $N(1\le N\le 10^5)$과 초기에 세미나를 신청한 부원의 수 $M(0\le M\le N)$과 쿼리의 개수 $Q(1\le Q\le 10^5)$이 공백으로 구분되어 주어진다.

두 번째 줄에 초기에 세미나를 신청한 $M$명의 서로 다른 번호 $s\_i(1\le s\_i\le N)$가 오름차순으로 공백으로 구분되어 주어진다. 이때, $M=0$이라면 빈 줄이 주어진다.

세 번째 줄부터 $N-1$ 줄에 걸쳐 트리의 간선 $e\_i$를 구성하는 두 정점 $u\_i,v\_i(1\le u\_i\<v\_i\le N)$와 간선의 비용 $w\_{e\_i}(1\le w\_{e\_i}\le 10^9)$가 공백으로 구분되어 주어진다.

다음 줄에 각 쿼리의 타입을 의미하는 $Q$개의 정수 $t\_i(1\le t\_i\le 3)$가 공백으로 구분되어 주어진다.

각 $Q$개의 쿼리에 대해 다음과 같이 $v\_i$가 결정된다.

• 첫 번째 쿼리($i=1$)의 경우 $v\_1=1$이다.

• 두 번째 쿼리부터는 $i$번째 쿼리의 정점 $v\_i$는 다음과 같이 직전 쿼리($i-1$번째 쿼리)에 의해 결정된다.

  • $i-1$번째 쿼리가 $1$번 쿼리 였다면, $i-1$번째 쿼리 실행 후 $S$의 원소의 개수를 $t$라 할 때, $v\_i=\left( \left( v\_{i-1}+t \right)\bmod N \right) +1$
  • $i-1$번째 쿼리가 $2$번 혹은 $3$번 쿼리 였다면, $i-1$번째 쿼리의 답이 $t$라 할 때, $v\_i=\left( \left( v\_{i-1}+t \right)\bmod N \right) +1$

$2$번 혹은 $3$번 쿼리가 주어질 때마다 정답을 한 줄에 한 개씩 출력한다. $2$번 혹은 $3$번 쿼리가 하나 이상 주어짐이 보장된다.