Problem Background

GZOI2017 D2T3

Problem Description

Within a school, there are two bike-sharing companies, Company A and Company B, competing against each other. Company A aims to increase its market share by hindering Company B's recovery operations.

The campus consists of $N$ areas connected by $M$ roads, each road linking two areas. Area $K$ is Company B's headquarters, from which all recovery operations start. To minimize costs, Company B chooses the shortest path from area $K$ to any area $X$. If there are multiple shortest paths to an area, Company B selects the one with the smallest preceding area number among all shortest paths. This path is called the recovery route from $K$ to $X$. All recovery routes form a tree structure known as the recovery route tree. In the figure below, the green edges form the recovery route tree.

Company B will recover bikes from several areas, called recovery areas. Company B also designates certain areas as deployment areas, with the remaining areas being non-deployment areas. On the recovery route tree, area $K$ is marked, along with all recovery areas and the nearest common ancestors of any two recovery areas.

In the figure below, assuming areas 4 and 6 are deployment areas, and areas 4, 5, and 6 are recovery areas, the marked areas are 1, 4, 5, and 6.

Company A hinders Company B's recovery operations if and only if for any marked deployment area $X$ other than $K$, there exist two marked areas on the recovery route from $K$ to $X$ such that all roads between them (the path on the recovery route tree) are blocked.

The cost of blocking a road is equal to its length. In the figure above, Company A chooses to block the paths $1 \rightsquigarrow 4$ and $5 \rightsquigarrow 6$, with a total cost of $3 + 4 + 3 = 10$.

Your task is to help Company A calculate the minimum cost to hinder Company B's recovery operations.

Input Format

The first line contains four integers $N, M, K, Q$, representing the number of areas, the number of roads, the headquarters number $K$ of Company B, and the number of operations, respectively.

The next $M$ lines describe the roads, each containing three integers $S, T, Len$, indicating a bidirectional road from $S$ to $T$ with length $Len$.

The following $Q$ lines describe the operations. Each line starts with an integer indicating the operation type. $0$ means Company B changes the deployment areas, and $1$ means a recovery operation by Company B.

For operation type $0$, it is followed by an integer $num$ and $num$ area numbers, indicating the areas being changed. If an area is a deployment area, it becomes a non-deployment area, and vice versa.

For operation type $1$, it is followed by an integer $num$ and $num$ area numbers, indicating the recovery areas. Each recovery operation requires re-marking on the recovery route tree.

Output Format

For each recovery operation, output a line indicating the minimum cost for Company A to hinder Company B. If there are no marked deployment areas, output $-1$.

Sample Input and Output

Input Sample #1

6 6 1 4
1 2 3
2 3 2
2 4 4
3 6 4
1 5 5
5 6 3
0 3 3 4 6
1 3 4 5 6
0 1 3
1 4 3 4 5 6

Output Sample #1

10
6

Input Sample #2

12 11 4 5
4 1 32
4 6 42
1 3 29
7 1 17
7 10 23
9 7 21
5 6 16
2 6 28
5 8 14
8 11 11
8 12 17
1 11 1 2 3 5 6 7 8 9 10 11 12
0 4 3 11 5 2
1 4 10 9 6 11
0 4 7 8 12 11
1 4 11 2 9 10

Output Sample #2

-1
41
77

Notes/Hints

Data Constraints

• For $30\%$ of the data, $N \le 200$, $Q \le 200$.
• For $60\%$ of the data, the number of recovery areas is always $N-1$.
• For $80\%$ of the data, $N \le 20000$, $M = N-1$, $Q \le 1000$, $\le 200$.
• For $100\%$ of the data, $N \le 50000$, $M \le 100000$, $Q \le 1500$, $\le 500$.

All data guarantee no self-loops, all road lengths are less than $2000$, and area $K$ is never a deployment area at any time.

见题面 Input 部分

见题面 Output 部分