26617번 - 선물교류

경곽나라에는 $1$부터 $N$까지 번호가 붙여진 $N$개의 마을이 있다.

처음에는 $N-1$개의 양방향도로로 모든 마을이 연결되어 있으며, 각 도로는 km 단위의 길이를 가지고 있다. 연결된 도로를 통해 이동할 수 있는 마을들은 같은 세력권을 형성하며, 세력권을 형성하고 있는 마을의 수가 많을수록 세력이 크다. 세력권을 형성하고 있는 마을은 트리로 나타나며, 이 트리의 센트로이드 중 가장 번호가 작은 곳을 세력권의 중심이라고 부른다. 경곽나라는 크리스마스날이 되면 마을에서 국왕 매스킹에게 선물을 보내고 국왕이 마을에 기념품을 하사하는 전통을 가지고 있으며, 국왕은 항상 최대 세력을 가지고 있는 세력권들의 중심 중에 가장 번호가 작은 마을에 위치한다.

하지만 올해 크리스마스날에는 다른 나라에서 경곽나라로 공격이 들어왔다. 공격으로 국왕이 있는 마을이 파괴되면 국왕은 즉시 그 마을과 연결된 모든 도로를 끊고 마을을 폐쇄하고 피신한다. 이때, 피신하는 마을은 기존과 같이 최대 세력을 가지는 중심 중 가장 번호가 작은 마을이다. 물론 국왕은 전지전능하기 때문에 도로를 사용하지 않고도 임의의 남아 있는 마을로 이동할 수 있다.

그럼에도 불구하고 크리스마스는 중요하기에, 국왕은 선물과 기념품의 교류를 계속하려 한다. 선물과 기념품은 반드시 최단경로로 운송되어야 하며, 운송 수단으로는 버스를 이용할 수 있다. 각 마을에는 자기 마을에서 하나의 물건을 싣고 같은 세력권 내의 다른 마을로 이동할 수 있는 버스가 있다. 이 버스들은 고유한 적재비용과 통일된 운송비용 시스템을 지니고 있다. 구체적으로, $i$번 마을의 버스인 $i$번 버스는 하나의 물건을 싣는 데 $C_{i}$원의 적재비용이 들고, 모든 버스는 $x$km를 이동하는 데 $x^{2}$원의 운송비용이 든다. 각 버스는 연결된 도로를 통해 물건을 운송할 수 있으며, 한 마을에 도착할 때마다 물건을 그 마을의 버스로 옮기거나 지금 버스를 계속 사용하는 두 가지 선택지 중 하나를 고를 수 있다. 각 교류가 끝난 후에, 운송비는 사용한 버스들의 적재비용과 운송비용을 모두 더한 값으로 정산된다. 또한, 각 교류가 끝나면 사용한 버스들이 자기 마을로 돌아가며, 이때는 운송을 하는 것이 아니기 때문에 어떤 비용도 들지 않는다. 국왕을 도와 선물과 기념품을 주고받을 때 드는 최소 비용을 구하여라.

구체적으로, 처리해야 하는 쿼리는 다음과 같다.

• $1$ $s$ $tp$ : $s$번 마을과 교류를 진행하는데, $tp = 1$인 것은 국왕이 선물을 받을 때, $tp = 2$일 때는 국왕이 기념품을 하사할 때 필요한 최소 운송비(원)를 출력한다.
• $2$ : 현재 국왕이 있는 마을이 공격을 받아 파괴된다.

* 센트로이드 : 해당 정점을 지웠을 때 쪼개지는 서브트리들의 크기가 모두 원래 트리 크기의 절반 이하가 되는 정점을 의미한다.

첫 줄에는 마을의 개수 $N$이 주어진다.

두 번째 줄 부터 $N-1$개 줄에 공백으로 구분된 세 개의 정수 $S$ $E$ $V$가 주어진다. 이는 마을 $S$와 마을 $E$를 연결하는 거리가 $V$인 도로가 있음을 의미한다.

그 다음 줄부터 $N$개의 줄에는 버스의 고유한 적재비용 $C_{i}$이 주어진다. 구체적으로, $i$번째에는 $i$번 버스의 물건 적재비용이 주어진다.

그 다음 줄에 쿼리의 개수 $Q$가 주어진다.

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 이때, 국왕이 항상 마을에 거주할 수 있음이 보장된다.

$1$번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다. 만약 주어진 마을과 국왕간의 교류가 불가하다면 $-1$을 출력한다. $1$번 쿼리에 이미 폐쇄된 마을이 주어질 수 있음에 유의하라.

• $2 \leq N \leq 10^{5}$
• $1 \leq V \leq 10^{4}$
• $1 \leq Q \leq 3 \times 10^{5}$
• $1 \leq C_{i} \leq 10^{9}$