You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述 10s 1024MB

小明有一天做梦，梦见自己来到了松鼠的王国。

松鼠的王国可以看成是一棵$n$个节点的树，根节点是$1$号。

每个节点$i$都有一家卖宝石的商店，会出售一种宝石，一共有$k_i$颗，每颗价格$w_i$。

小明从时间$T$从根节点出发，带着$C$的钱一路向下，走到出口节点$X$就会回到现实世界。

这个过程中，小明可以花钱买宝石，直到花光钱为止。为了带更多的宝石回到现实世界，小明希望自己买的宝石尽量便宜。但是，松鼠们有点懒散，每家宝石的开门时间是不一样的，第$i$个节点的宝石商店，开门时间是$t_i$，也就是，从$t_i$以后，才能在这个商店买宝石。

但是小明没有更多的时间，他必须在时间$T$快速的沿着最近的路径走到$X$，以及在路上购买宝石。

他一共有$Q$次计划，第$i$次计划，是$T_i$时间从根节点出发，带着$C_i$的钱，走到$X_i$以后回到现实世界（这期间时间都停留在$T_i$）。

请帮小明算一下，他每次计划里，买到的最贵的宝石的价格是多少，如果一颗宝石都没有买到，则认为是$0$。

输入格式

第一行输入$n$。

接下来$n$行，每行三个数字$k_i,w_i,t_i$。

接下来$n-1$行，每行输入$u,v$，表示一条树边。

接下来一个数字$Q$。

接下来$Q$行，每行三个数字$T_i,C_i,X_i$。

输出格式

输出$Q$行，表示每一次询问的答案。

5
2 2 2
2 3 1
2 4 3
2 1 4
2 1 2
1 2
2 3
3 4
3 5
7
1 12 4
1 5 4
1 2 4
4 7 4
4 9 4
3 13 4
3 14 4

3 3 0 2 3 3 4

数据范围

对于20%的数据：$n,Q\leq 1000$。

对于另15%的数据：保证$t_i=1$。

对于另10%的数据：保证$v=2u$或者$v=2u+1$。

对于另20%的数据：保证$v=u+1$。

对于100%的数据：$n,Q\leq 10^5,1\leq k_i\leq 10^5,1\leq t_i,w_i,T_i,X_i\leq n,1\leq C_i\leq 10^{15}$。