Trains and Airplanes
Contest: Hello 2022
Difficulty rating: 3500
Tags: dfs and similar, graphs, shortest paths, trees

Railway network of one city consists of $$$n$$$ stations connected by $$$n-1$$$ roads. These stations and roads forms a tree. Station $$$1$$$ 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 $$$dist(v)$$$ as the time that trains spend to get from the station $$$v$$$ to the station $$$1$$$.

This railway network is splitted into zones named by first $$$k$$$ capital latin letters. The zone of the $$$i$$$-th station is $$$z_i$$$. 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 station $$$v$$$ to station $$$1$$$ happends:

- At the moment $$$0$$$, tourist enters the train that follows directly from the station $$$v$$$ to the station $$$1$$$. The trip will last for $$$dist(v)$$$ minutes.
- Tourist can buy tickets for any subset of zones at any moment. Ticket for zone $$$i$$$ costs $$$pass_i$$$ euro.
- Every $$$T$$$ minutes since the start of the trip (that is, at the moments $$$T, 2T, \ldots$$$) the control system will scan tourist. If at the moment of scan tourist is in the zone $$$i$$$ without zone $$$i$$$ ticket, he should pay $$$fine_i$$$ euro. Formally, the zone of tourist is determined in the following way:   If tourist is at the station $$$1$$$, then he already at the city center so he shouldn't pay fine.  If tourist is at the station $$$u \neq 1$$$, then he is in the zone $$$z_u$$$.  If tourist is moving from the station $$$x$$$ to the station $$$y$$$ that are directly connected by road, then he is in the zone $$$z_x$$$.  Note, that tourist can pay fine multiple times in the same zone.

Tourist always selects such way to buy tickets and pay fines that minimizes the total cost of trip. Let $$$f(v)$$$ be such cost for station $$$v$$$.

Unfortunately, tourist doesn't know the current values of $$$pass_i$$$ and $$$fine_i$$$ for different zones and he has forgot the location of the airport. He will ask you queries of $$$3$$$ types:

- $$$1$$$ $$$i$$$ $$$c$$$ — the cost of ticket in zone $$$i$$$ has changed. Now $$$pass_i$$$ is $$$c$$$.
- $$$2$$$ $$$i$$$ $$$c$$$ — the cost of fine in zone $$$i$$$ has changed. Now $$$fine_i$$$ is $$$c$$$.
- $$$3$$$ $$$u$$$ — solve the following problem for current values of $$$pass$$$ and $$$fine$$$:   You are given the station $$$u$$$. Consider all the stations $$$v$$$ that satisfy the following conditions:   $$$z_v = z_u$$$  The station $$$u$$$ is on the path from the station $$$v$$$ to the station $$$1$$$.  Find the value of $$$\min(f(v))$$$ over all such stations $$$v$$$ with the following assumption: tourist has the ticket for the zone of station $$$z_u$$$.

Input format:
The first line contains the single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of stations.

Each of the next $$$n - 1$$$ lines contains three integers $$$v_i$$$, $$$u_i$$$, $$$t_i$$$ ($$$1 \leq v_i, u_i \leq n, 1 \leq t_i \leq 10^9$$$) — the ends of the $$$i$$$-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 $$$k$$$ ($$$1 \leq k \leq 26$$$) — the number of zones.

The next line contains $$$n$$$ symbols $$$z_1z_2 \ldots z_n$$$ — $$$z_i$$$ is the name of the zone of the $$$i$$$-th station. It is guaranteed that the conditions from the second paragraph are satisfied.

The next line contains $$$k$$$ integers $$$pass_1$$$, $$$pass_2$$$, $$$\ldots$$$, $$$pass_k$$$ ($$$1 \leq pass_i \leq 10^9$$$) — initial costs of tickets.

The next line contains $$$k$$$ integers $$$fine_1$$$, $$$fine_2$$$, $$$\ldots$$$, $$$fine_k$$$ ($$$1 \leq fine_i \leq 10^9$$$) — initial fines.

The next line contains the single integer $$$T$$$ ($$$1 \leq T \leq 10^9$$$) — the time gap between scans of control system.

The next line contains the single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

Next $$$q$$$ lines contains queries as described in the statement. It is guaranteed that in the queries of the first and the second type $$$i$$$ is a correct name of the zone (one of the first $$$k$$$ capital latin letters) and $$$1 \leq c \leq 10^9$$$, and in the queries of the third type $$$1 \leq u \leq n$$$.

Output format:
For each query of the third type print the answer to it.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Note, that the fine can be cheaper than the pass.

The railway network from the example. Green color is used for stations and roads of zone A, blue color is used for zone B and red color is used for zone D. The integer near each road is time that trains spend to pass it.

In the first query, the airport can be located near the station $$$2$$$ or near the station $$$4$$$. During the trip, tourist will always stay in the zone A. He already has the pass for this zone so the answer is $$$0$$$.

After the second query, the cost of the pass in the zone A has become $$$10$$$.

In the third query, the airport can be located only near the station $$$3$$$. Optimal solution will be to buy the pass for zone A. During the first $$$3$$$ 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 $$$4$$$-th and the $$$8$$$-th second of his ride. Since he have a pass for this zone, he won't pay fines.

After the forth query, the fine in the zone A has become $$$3$$$.

In the fifth query, the airport can be located only near the station $$$7$$$ and $$$f(7) = 6$$$.

In the sixth query, the airport can be located near the station $$$6$$$ or near the station $$$8$$$. Since $$$f(6)=9$$$ and $$$f(8)=6$$$ the answer is $$$6$$$.

Example input:
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

Example output:
0
10
6
6

Editorial:
Let $$$scans_{v, i}$$$ be the number of scans in the $$$i$$$-th zone if we start from the vertex $$$v$$$ and $$$scans_{v, z_v} = 0$$$.
Note that $$$scans$$$ doesn't change during queries.
Now our task is to calculate $$$\sum_{z \in zones} \min (scans_{v, z} \cdot fine_{z}, pass_{z})$$$ over some set of vertices $$$A_i$$$ described in the $$$i$$$-th query.
It is important to note that for any two vertices $$$v_1, v_2 \in A_i$$$ and any zone $$$z$$$ holds $$$|scans_{v_1, z} - scans_{v_2, z}| \leq 1$$$. From this, we can see that there are no more than $$$\mathcal{O}(2^k)$$$ different values of $$$scans_v$$$ for $$$v \in A_i$$$, so we don't need to check all vertices in $$$A_i$$$ to find the answer. However, it is still quite a lot.
Let $$$minscans_z$$$ be the min value of $$$scans_{v, z}$$$ for $$$v \in A_i$$$. For some vertices $$$v$$$ we will have $$$minscans_z$$$ scans in zone $$$z$$$ and $$$minscans_z + 1$$$ scans for other vertices.
Actually, we can look at the moment $$$t$$$ we escape the start zone (zone that contains the airport). For each zone $$$z$$$ there is a segment$$$\bmod T$$$ such that if $$$t$$$ lies in it we will have $$$minscans_z$$$ scans in this zone and we will have $$$minscans_z + 1$$$ scans otherwise.
Let's suppose we are going to do something like sweepline on this segments. There are $$$\mathcal{O}(k)$$$ segments and they can split the$$$\bmod T$$$ circle into at most $$$\mathcal{O}(k)$$$ sections. This is how we get that we actually should check not more that $$$2k$$$ vertices in order to find answer for each query.
What about the implementation part, we should be able to find where we escape the start zone (let's call this vertex $$$V$$$) and the time we spend on the road from any vertex to the vertex $$$1$$$. It can be easily done with dfs. Also we should be able to calculate $$$scans_{V}$$$. We can do it in $$$\mathcal{O}(k)$$$ by repeatedly going to the next vertex of the path in another zone. While doing this we can also find$$$\bmod T$$$ segments when we should escape the start zone in order to have less scans in each zone: if we start from vertex $$$V$$$ and we are in the zone $$$z$$$ at the segment of moments $$$[t_l, t_r]$$$, then we will have to pay additional fine in zone $$$z$$$ if we pass through $$$V$$$ at one of moments $$$[T-t_r, T-t_l] \pmod T$$$. Then we will do sweepline algorithm on this segments to find the segments of times we are interested in. The last thing we should be able to do is to determine in which of previouly descibed segments there are vertices in $$$A_i$$$. It can be done by computing this segment for each vertex and then merging this values by dfs.
During answering the query we can iterate over all previouly descibed segments and update answer in case we have vertex in this segment. In order to reduce time complexity of answering query from $$$\mathcal{O}(k^2)$$$ to $$$\mathcal{O}(k)$$$ we should actually perform such sweepline and maintain current answer and precompute whether we have vertices in this section.
It is how we can get $$$\mathcal{O}(nk\log k + qk)$$$ solution with $$$\mathcal{O}(nk)$$$ memory. We can also do all calculations in place and solve this problem with $$$\mathcal{O}(n)$$$ memory in $$$\mathcal{O}(nk\log k + qk\log k)$$$ which is not much slower.
It seems that this problem is somehow connected with real life so you can be interested how such descripion of set of vertices in queries was obtained. Assume that tourist already was in this airport. He bought the ticket at the station near the airport but activated it only at the station $$$u$$$ in the same zone. At the moment of query he had this ticket and it contained some information about activation.
Bonus (unsolved): can you support some of the other change queries (road lengths, tree structure, zones of stations, constant $$$T$$$)?