CF1621H.Trains and Airplanes

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$.

某城市的铁路网络由 $n$ 个车站和 $n-1$ 条道路构成，这些车站与道路构成一棵树。其中，车站 $1$ 为城市中心。每条道路均标有列车通过该道路所需的时间（可假设列车在车站不停靠）。定义 $dist(v)$ 为列车从车站 $v$ 到达车站 $1$ 所需的时间。

该铁路网络被划分为若干区域，区域名称依次为前 $k$ 个大写拉丁字母（即 A、B、C、…）。第 $i$ 个车站所属的区域为 $z_i$。城市中心（车站 $1$）位于区域 A。对于其余所有车站，保证：从该车站通往城市中心路径上的第一个车站，其所在区域要么与该车站相同，要么其区域名称字典序更小。每条道路完全归属于距离城市中心更远一端所处的区域。

一名游客即将抵达机场，随后将前往城市中心。他从车站 $v$ 前往车站 $1$ 的行程规则如下：

• 在时刻 $0$，游客登上一列从车站 $v$ 直接驶向车站 $1$ 的列车，整个行程耗时 $dist(v)$ 分钟。
• 游客可在任意时刻购买任意子集区域的车票；购买区域 $i$ 的车票需花费 $pass_i$ 欧元。
• 自行程开始起，每隔 $T$ 分钟（即在时刻 $T, 2T, \ldots$），检票系统将对游客进行一次扫描。若在扫描时刻，游客身处区域 $i$ 却未持有该区域车票，则须缴纳罚款 $fine_i$ 欧元。具体而言，游客所在区域按如下规则确定：
  • 若游客位于车站 $1$，则已抵达城市中心，无需缴纳罚款；
  • 若游客位于车站 $u \neq 1$，则其所在区域为 $z_u$；
  • 若游客正在沿一条直接连接车站 $x$ 与车站 $y$ 的道路行驶，则其所在区域为 $z_x$。
    注意：游客可能在同一区域内多次被罚款。

游客总以最小化行程总成本的方式决定购票与缴纳罚款策略。令 $f(v)$ 表示从车站 $v$ 出发的最小总成本。

不幸的是，游客并不知晓当前各区域的 $pass_i$ 和 $fine_i$ 值，也忘记了机场所在的车站。他将向你提出以下三类查询：

• 1 i c —— 区域 $i$ 的车票价格更新为 $c$，即 $pass_i \gets c$；

• 2 i c —– 区域 $i$ 的罚款金额更新为 $c$，即 $fine_i \gets c$；

• 3 u —– 对当前的 $pass$ 和 $fine$ 值，求解以下问题：
  给定车站 $u$，考虑所有满足以下条件的车站 $v$：

  • $z_v = z_u$；
  • 车站 $u$ 位于从车站 $v$ 到车站 $1$ 的路径上。

  在游客已持有车站 $z_u$ 所在区域车票的前提下，求所有此类车站 $v$ 对应的 $f(v)$ 的最小值。

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$.

第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 车站的数量。

接下来的 $n - 1$ 行每行包含三个整数 $v_i$、$u_i$、$t_i$（$1 \leq v_i, u_i \leq n$，$1 \leq t_i \leq 10^9$）—— 表示第 $i$ 条道路的两个端点以及列车通过该道路所需的时间。保证这些道路构成一棵树。

接下来一行包含一个整数 $k$（$1 \leq k \leq 26$）—— 区域的数量。

接下来一行包含 $n$ 个字符 $z_1z_2 \ldots z_n$ —— 其中 $z_i$ 表示第 $i$ 个车站所属的区域名称。保证满足题面第二段所述的条件。

接下来一行包含 $k$ 个整数 $pass_1$、$pass_2$、$\ldots$、$pass_k$（$1 \leq pass_i \leq 10^9$）—— 各区域车票的初始费用。

接下来一行包含 $k$ 个整数 $fine_1$、$fine_2$、$\ldots$、$fine_k$（$1 \leq fine_i \leq 10^9$）—— 各区域违规罚款的初始金额。

接下来一行包含一个整数 $T$（$1 \leq T \leq 10^9$）—— 控制系统扫描的时间间隔。

接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）—— 查询的数量。

接下来的 $q$ 行按题面描述给出查询。保证在第一类和第二类查询中，$i$ 是一个合法的区域名称（即前 $k$ 个大写拉丁字母之一），且 $1 \leq c \leq 10^9$；在第三类查询中，$1 \leq u \leq n$。

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

对于每个第三种类型的查询，请输出其答案。

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$.

注意，罚款可能比通行证便宜。

示例中的铁路网络。绿色表示 A 区的车站和轨道，蓝色表示 B 区，红色表示 D 区。每条轨道旁的整数表示列车通过该轨道所需的时间（单位：秒）。

在第一个查询中，机场可设在车站 $2$ 附近或车站 $4$ 附近。旅途中，游客始终停留在 A 区。他已持有该区的通行证，因此答案为 $0$。

第二个查询后，A 区通行证的价格变为 $10$。

第三个查询中，机场只能设在车站 $3$ 附近。最优方案是购买 A 区的通行证。在行程的前 $3$ 秒内，游客位于 B 区；随后进入 A 区，并将在乘车的第 $4$ 秒和第 $8$ 秒被扫描。由于他持有该区通行证，故无需缴纳罚款。

第四个查询后，A 区的罚款金额变为 $3$。

第五个查询中，机场只能设在车站 $7$ 附近，且 $f(7) = 6$。

第六个查询中，机场可设在车站 $6$ 附近或车站 $8$ 附近。由于 $f(6)=9$ 且 $f(8)=6$，因此答案为 $6$。