LKP '18 Contest 2 P6 - Reconstruction

View as PDF

Submit solution

Points: 25
Time limit: 1.8s
Memory limit: 256M

Authors:
Problem types

During Collea's war with The Alliance, Collea faced massive bombardments all across the country, destroying or damaging most of the roads and infrastructure within the country. There are currently N cities in the country of Collea, where K of them are considered crucial to the country. Currently, there are N-1 roads in Collea that are reparable within the month, the ith of which connecting cities a_i and b_i while costing c_i Freitz. Note that each road only connects two cities in Collea and that if all the roads were repaired, it would be possible to travel from any city to all other cities in Collea while only using these roads. During the course of the war, M reports of two different types are received. Reports of type 1 give a city number c, and details that if c is currently an unimportant city, it would be deemed crucial, and if it was already a crucial city, it would be deemed as unimportant. Reports of type 2 details that the cost of repairing the rth road is changed to u Freitz. Burdened by war reparations, the Collean government needs to find the minimal cost of connecting all of their crucial cities within the month. Help them find this minimum cost initially, and after each report.

Constraints

1 \le N \le 100\,000
0 \le M \le 100\,000
1 \le K \le N
1 \le c_i \le 10^6

Subtask 1 [10%]

M=0

Subtask 2 [25%]

All reports are of type 1.

Subtask 3 [65%]

No additional constraints.

Input Specification

The first line will contain three positive integers, N, M, and K.
The next line will contain K positive integers, the original crucial cities of Collea.
N-1 lines will follow, the ith of which containing the integers a_i, b_i, and c_i.
M more lines will follow, each one in the form of either 1 c or 2 r u, describing the type and parameters of the report.

Output Specification

On the first line, print the initial minimal cost of connecting all of the crucial cities of Collea.
Output M more lines, the ith of which containing one integer, the minimal cost of connecting all of the crucial cities of Collea after the ith report.

Sample Input

5 2 2
2 5
2 4 3
1 2 1
3 2 2
5 1 4
1 3
2 2 5

Sample Output

5
7
11

Comments


  • 3
    Plasmatic  commented on Aug. 19, 2020, 2:04 a.m. edit 2

    I think data for this problem are weak. Master Acutie (AQT) today informed me that my LCA implementation for HLD is incorrect but it still passed for this problem.

    (Presumably) incorrect submission


    • 2
      Tzak  commented on Aug. 19, 2020, 8:09 p.m.

      IMQT orz