一道水题-hard

题目描述

现在有n个阀门标号为1~n，m条管道连通了它们（连通的阀门之间不会有环），每个阀门都对应了一个$a_i$,每个管道存在一个边权$c_i$.

$a_i$为一个阀门放出的水流的扩散系数，$c_i$代表了水流通过这个管道会损失多少扩散系数。

当一个阀门放水时，会向他所连通的每个管道放出扩散系数相同为$a_i$的水，当每条水流的扩散系数大于等于当前管道的损失量时，才能到达下一个阀门，同时扩散系数减少$c_i$。

当一个阀门接收到扩散系数为t的水时，会向他所连通的每个管道（除了接收的管道）放出扩散系数相同为t的水流，水流扩散规则不变。

当放水一个阀门停止放水后，所有因它产生的水流消失。

小波有能出现在所有水里的能力，他想偷到若干个阀门的控制器，他在同一时间内只能打开其中一个阀门实现移动（所以不会有水流叠加的情况），他能够通过打开不同的阀门，来实现移动。 但是所有的控制器排成了一条长串$s$，小波一次只能偷其中的一个子串中的控制器，所以他给了你q条询问,每个询问包括一个l,r代表子串区间，他希望你回答当他偷取这个区间的控制器时，能够移动到多少个阀门。 数据范围和限制与easy有所不同

数据保证生成管道图一定为树，至于为什么会设置m条边，就当出题人脑子抽了吧

小波有能出现在所有水里的能力是指：当一个阀门里有水时，即便它的扩散系数为0，他也能无视任何条件出现在这个阀门，即使他当前在一个没水的阀门，他也能移动到有水的阀门 数据保证$len(s)*n \le1e6 ,q \le 1e5)$

输入格式

第一行输入四个正整数$n,m,q,s$ $(1 \le n\le 1e5 ,m =n-1 ,1 \le q \le 1e5,1 \le s \le 1e5)$ $数据保证 s*n\le 1e6$ $n$代表存在$n$个阀门，$m$代表存在$m$条管道,$q$代表一共有q次询问,$s$代表

第二行输入n个正整数$a_i$,$(1 \le a_i \le 100000)$$a_i$代表第$i$个阀门放水的扩散系数。

第三行输入s个正整数$b_i$,$(1 \le b_i \le n)$$b_i$代表第$b_i$个阀门的控制器 接下来$m$行，每行输入三个正整数$u,v,c$ $(1\le u,v \le n ，1\le c \le 5000)$ $u,v$代表管道的两端，$c$代表该条管道所需的扩散系数 接下来$q$行，每行输入两个数$l,r$$(1 \le l \le r \le s)$代表询问区间

输出格式

输出$q$行，每行输出一个正整数代表这个区间控制器移动到的阀门数。

样例 #1

样例输入 #1

10 9 10 5
100 100 100 100 100 100 100 100 100 100
4 2 4 5 2 
1 7 50
1 2 50
2 6 50
2 3 50
3 8 50
1 4 100
4 10 100
4 5 100
4 9 100
1 1
2 2
4 4
1 2
2 4
3 4 
4 5
1 5
3 5 
2 3

样例输出 #1

5
6
2
10
10
5
8
10
10
10