JOI 나라에는 N개의 도시가 있다. 이 도시들은 1번부터 N번까지 번호가 붙어있다. 이 도시에는 N-1개의 도로가 있고, 1번부터 N-1번까지의 번호가 붙어있다. i번 (1 ≤ i ≤ N-1) 도로는 노선이 두개가 있다. 한 노선은 A_i번 도시에서 B_i번 도시로 향하는 노선이고, 다른 노선은 B_i번 도시에서 A_i번 도시로 향하는 노선이다. 즉, 모든 도로는 양방향이다. 어떤 두 도시간에도 몇개의 도로를 사용해서 이동하는 것이 가능하다.

처음에 모든 노선들은 정비되어있지 않다. 각 도로의 각 노선에 대해, 우리는 노선을 정비하는 비용을 알고 있다. i번 (1 ≤ i ≤ N-1) 도로의 A_i번 도시에서 B_i번 도시로 향하는 노선을 정비하는 비용은 C_i이고, B_i번 도시에서 A_i번 도시로 향하는 노선을 정비하는 비용은 D_i이다.

JOI 나라의 장관인 K 이사장은 몇몇 도시를 골라 그 도시를 특별관광도시로 만들것이다. x번 (1 ≤ x ≤ N)을 특별관광도시로 만들 때, 각 도로 i (1 ≤ i ≤ N-1)에 대해, 다음 일이 일어날 것이다.

i번과 B_i번 도시 중에서 x번 도시에 가까운 도시는 a번 도시이고, 먼 도시는 b번 도시라고 하자. 여기서, 가까운 도시라고 함은 x번 도시에 가기 위해 사용해야 하는 도로의 수가 더 적은 도시를 말한다. 이 때, b번 도시에서 a번 도시로 향하는 노선이 정비되지 않은 상태라면 정비된다.

특별관광도시를 만들기 위해 노선을 정비하는 비용은 세금으로 충당되지만, 특별관광도시가 만들어 진 이후에 남은 도로를 정비하는 비용은 K 이사장의 개인 자금에서 나간다.

K 이사장이 계획한 Q개의 계획이 있다. j번째 (1 ≤ j ≤ Q) 계획에서는, 그는 특별관광도시가 없고 모든 노선이 정비되지 않은 상태에서 시작해서 정확히 E_j개의 도시를 특별관광도시로 만들것이다. 하지만, 어떤 도시들이 특별관광도시가 될지는 계획되지 않았다. 그는 개인 자금에서 나가는 도로 정비 비용을 최소로 하고 싶다.

JOI 나라의 도시 수, 도로의 정보와 계획의 정보가 주어졌을 때, 각 계획마다 K이사장의 개인 자금에서 나가는 도로 정비 비용을 최소로 하는 프로그램을 작성하여라.

[입력제한]

2 ≤ N ≤ 200,000

1 ≤ A_i ≤ N (1 ≤ i ≤ N)

1 ≤ B_i ≤ N (1 ≤ i ≤ N)

A_i != B_i

어떤 두 도시간에도 몇개의 도로를 사용해서 이동하는 것이 가능하다.

0 ≤ C_i ≤ 1,000,000,000 (1 ≤ i ≤ N)

0 ≤ D_i ≤ 1,000,000,000 (1 ≤ i ≤ N)

1 ≤ Q ≤ N

1 ≤ E_i ≤ N (1 ≤ j ≤ Q)

#3626 upload 5회 done 4회 how_to_reg 4명

특별관광도시 timer 2초 memory 512MB

#3626

특별관광도시 2초 512MB