Trains and Airplanes solution codeforces
Railway network of one city consists ofstations connected by roads. These stations and roads forms a tree. Station is a city center. For each road you know the time trains spend to pass this road. You can assume that trains don’t spend time on stops. Let’s define as the time that trains spend to get from the station to the station .
This railway network is splitted into zones named by firstcapital latin letters. The zone of the -th station is . City center is in the zone A. For all other stations it is guaranteed that the first station on the road from this station to the city center is either in the same zone or in the zone with lexicographically smaller name. Any road is completely owned by the zone of the most distant end from the city center.
Tourist will arrive at the airport soon and then he will go to the city center. Here’s how the trip from stationto station happends:
- At the moment , tourist enters the train that follows directly from the station to the station . The trip will last for minutes.
- Tourist can by tickets for any subset of zones at any moment. Ticket for zone costs euro.
- If tourist is at the station , then he already at the city center so he shouldn’t pay fine.
- If tourist is at the station , then he is in the zone .
- If tourist is moving from the station to the station that are directly connected by road, then he is in the zone .
Note, that tourist can pay fine multiple times in the same zone.
minutes since the start of the trip (that is, at the moments ) the control system will scan tourist. If at the moment of scan tourist is in the zone without zone ticket, he should pay euro. Formally, the zone of tourist is determined in the following way:
Tourist always selects such way to buy tickets and pay fines that minimizes the total cost of trip. Letbe such cost for station .
Unfortunately, tourist doesn’t know the current values ofand for different zones and he has forgot the location of the airport. He will ask you queries of types:
- ticket in zone has changed. Now is . — the cost of
- fine in zone has changed. Now is . — the cost of
— solve the following problem for current values of and :
- You are given the station
- The station is on the path from the station to the station .
Find the value of tourist has the ticket for the zone of station .over all such stations with the following assumption:
. Consider all the stations that satisfy the following conditions:
- You are given the station
The first line contains the single integer( ) — the number of stations.
Each of the nextlines contains three integers , , ( ) — the ends of the -th road and the time it takes a train to pass this road. It is guaranteed that this roads forms a tree.
The next line contains the single integer( ) — the number of zones.
The next line containssymbols — is the name of the zone of the -th station. It is guaranteed that the conditions from the second paragraph are satisfied.
The next line containsintegers , , , ( ) — initial costs of tickets.
The next line containsintegers , , , ( ) — initial fines.
The next line contains the single integer( ) — the time gap between scans of control system.
The next line contains the single integer( ) — the number of queries.
Nextlines contains queries as described in the statement. It is guaranteed that in the queries of the first and the second type is a correct name of the zone (one of the first capital latin letters) and , and in the queries of the third type .
For each query of the third type print the answer to it.
8 1 2 7 2 3 4 2 4 3 4 5 1 5 6 6 4 7 10 6 8 6 4 AABABBDB 11 12 10 42 16 15 15 30 4 6 3 2 1 A 10 3 3 2 A 3 3 7 3 6
0 10 6 6
Note, that the fine can be cheaper than the pass.
After the second query, the cost of the pass in the zone A has become .
In the third query, the airport can be located only near the station A. During the first seconds of trip tourist will be in the zone B. Then he will move to the zone A and will be scanned there on the -th and the -th second of his ride. Since he have a pass for this zone, he won’t pay fines.. Optimal solution will be to buy the pass for zone
After the forth query, the fine in the zone A has become .
In the fifth query, the airport can be located only near the stationand .
In the sixth query, the airport can be located near the stationor near the station . Since and the answer is .