#P5465. [PKUSC2018] 星际穿越

[PKUSC2018] 星际穿越

题目描述

nn 个星球,它们的编号是 1 到 nn,它们坐落在同一个星系内,这个星系可以抽象为一条数轴,每个星球都是数轴上的一个点,特别地,编号为 ii 的星球的坐标是 ii

一开始,由于科技上的原因,这 nn 个星球的居民之间无法进行交流,因此他们也不知道彼此的存在。现在,这些星球独立发展出了星际穿越与星际交流的工具。对于第 ii 个星球,他通过发射强力信号,成功地与编号在 [li,i1][l_i,i-1] 的所有星球取得了联系(编号为 1 的星球没有发出任何信号),取得联系的两个星球会建立 双向 的传送门,对于建立了传送门的两个星球 u,vu,vuu 上的居民可以花费 1 单位时间传送到 vvvv 上的居民也可以花费 1 单位时间传送到 uu ,我们用 dist(x,y)dist(x,y) 表示从编号为 xx 的星球出发,通过一系列星球间的传送门,传送到编号为 yy 的星球最少需要花费的时间。

现在有 qq 个星际商人,第 ii 个商人初始所在的位置是 xix_i, 他的目的地是 [li,ri][l_i,r_i] 中的其中一个星球,保证 li<ri<xil_i<r_i<x_i 。他会在这些星球中等概率挑选一个星球 yy (每个星球都有一样的概率被选中作为目的地),然后通过一系列星球的传送门,花费最少的时间到达星球 yy 。商人想知道他花费的期望时间是多少?也就是计算 $\frac{1}{r_i-l_i+1}{\sum_{y=l_i}^{r_i}{dist(x_i,y)}}$ 。

输入格式

第一行一个正整数 nn ,表示星球的个数。

第二行 n1n-1 个正整数,第 ii 个正整数为 li+1l_{i+1} ,表示编号在 [li+1,i][l_{i+1},i] 区间内所有星球已经与编号为 i+1i+1 的星球取得了联系,并且可以通过花费 1 单位进行彼此的传输。保证 li+1il_{i+1}\leq i

第三行一个正整数 qq ,表示询问组数。

接下来 qq 行,每行三个数字 li,ri,xil_i,r_i,x_i ,表示在 [li,ri][l_i,r_i] 这个区间中等概率选择一个星球 yydist(xi,y)dist(x_i,y) 的期望。保证 li<ri<xil_i<r_i<x_i

输出格式

对于每组询问,注意到答案必然是一个有理数,因此以 p/qp/q 的格式输出这个有理数,要求 gcd(p,q)=1\gcd(p,q)=1

如果答案为整数 mm ,输出 m/1m/1

7
1 1 2 1 4 6
5
3 4 6
1 5 7
1 2 4
1 2 6
1 3 5
3/2
13/5
3/2
2/1
1/1

提示

样例对应的无向图如下:ex

对于 20%20\% 的数据,满足 n100n \leq 100

对于另 25%25\% 的数据,满足 n2000n\leq 2000

对于另 25%25\% 的数据,满足 n5000n\leq 5000

对于 100%100\% 的数据,满足 n,q3×105n,q\leq 3\times 10^5