Trains and Airplanes

题意翻译

A 城的铁路系统由 $n$ 个站点和 $n-1$ 条铁路组成，这些站点和铁路共同组成了一棵树。站点 $1$ 是市中心。对于第 $i$ 条铁路，你都知道它连接的两个站点 $v_i,u_i$ 以及火车经过它需要的时间 $t_i$，并且你可以假设**火车停靠站点不需要时间**。我们定义 $dist(v)$ 为从站点 $v$ 坐火车到站点 $1$ 需要的时间。 与此同时，A 城的铁路系统被分成了 $k$ 个区域，每个区域以字母表中前 $k$ 个大写字母中的一个命名。站点 $i$ 所在的区域为 $z_i$，站点 $1$ 在区域 A。对于所有其他的站点，保证从该站点到站点 $1$ 的路径上经过的第一个站点所在的区域名和该站点相同或者是比该站点所在的区域名的字典序小的大写字母。**任何一条铁路都完全属于离市中心最远的站点所在的区域**。 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 慕名前往 A 城，他到达机场之后将前往市中心游览。他从站点 $v$ 到站点 $1$ 的行程可能是这样的： - 在 $0$ 时刻，$\color{black}\textsf{t}\color{red}\textsf{ourist}$ 进入从站点 $v$ 直达站点 $1$ 的火车，行程将持续 $dist(v)$ 分钟。 - 在任意时刻，$\color{black}\textsf{t}\color{red}\textsf{ourist}$ 可以买任意几个区域的车票。第 $i$ 个区域的车票价格为 $pass_i$ 欧元。 - 每 $T$ 个时刻，控制系统将会扫描 $\color{black}\textsf{t}\color{red}\textsf{ourist}$。如果此时 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 在区域 $i$ 而没有区域 $i$ 的车票，他将付 $fine_i$ 欧元的罚金。注意，在同一个区域，$\color{black}\textsf{t}\color{red}\textsf{ourist}$ 可能会交多次罚金。形式化的说，$\color{black}\textsf{t}\color{red}\textsf{ourist}$ 所在的区域由以下方式决定： - 如果 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 在站点 $1$，则他已经到达了市中心，因此他不需要交任何罚金。 - 如果 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 在站点 $u(u\neq 1)$，则他在区域 $z_u$。 - 如果 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 在从站点 $x$ 到站点 $y$ 的一条铁路上，则他在区域 $z_x$。 由于 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 很强，因此他知道如何购买车票和支付罚金来最小化整个行程的花费。定义 $f(v)$ 为 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 从站点 $v$ 出发到站点 $1$ 的最小花费。不幸的是，$\color{black}\textsf{t}\color{red}\textsf{ourist}$ 并不知道当前 $pass_i$ 和 $fine_i$ 的值，而且他也忘记了机场在哪一个站点。因此，他会向你提出 $q$ 次询问，每次他可以向你提出如下三种询问中的一种： - `1 i c`：将 $pass_i$ 替换为 $c$。 - `2 i c`：将 $fine_i$ 替换为 $c$。 - `3 u`：依照当前的 $pass$ 和 $fine$ 数组的值解决下列问题： - 给定一个站点的编号 $u$，假设 $\color{black}\textsf{t}\color{red}\textsf{ourist}$ 已经买好了区域 $z_u$ 的车票。对于所有满足下列条件的 $v$： - $z_u=z_v$； - 站点 $u$ 在从站点 $v$ 到站点 $1$ 的路径上。 求 $\min(f(v))$。 请你完成这 $q$ 次询问。 数据范围： - $2\leqslant n\leqslant 2\times 10^5$，$1\leqslant k\leqslant 26$，$1\leqslant T\leqslant 10^9$，$1\leqslant q\leqslant 2\times 10^5$。 - $1\leqslant t_i,pass_i,fine_i,c\leqslant 10^9$，$1\leqslant v_i,u_i\leqslant n$。 Translated by Eason_AC 2022.1.4

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

0
10
6
6

说明

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