Solution 

倍增

Code 

#include 
    
     #define reg register#define ll long longusing namespace std;int read() {    int x = 0, f = 1;    char ch = getchar();    while (ch < '0' || ch > '9') {        if (ch == '-')            f = -1;        ch = getchar();    }    while (ch <= '9' && ch >= '0') {        x = (x << 1) + (x << 3) + ch - '0';        ch = getchar();    }    return x * f;}const int MN = 3e5 + 5;int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }int N, l[MN];int p[MN][20], v[MN][20];int cal(int L, int x) {    if (L == x)        return 0;    if (L >= l[x])        return x - L;    int r = x - L, step = 0, i;    for (x = l[x], i = 18; ~i; --i)        if (p[x][i] >= L) {            r += v[x][i] + (x - p[x][i]) * step;            step += 1 << i;            x = p[x][i];        }    r += (x - L) * (step + 1);    return r;}int main() {    N = read();    reg int i, j;    for (l[1] = 0, i = 2; i <= N; ++i) l[i] = read();    for (p[N][0] = l[N], i = N - 1; i; --i) p[i][0] = min(l[i], p[i + 1][0]);    for (j = 1; j <= 18; ++j)        for (i = 1; i <= N; ++i)            if (p[i][j - 1])                p[i][j] = p[p[i][j - 1]][j - 1];    for (i = 1; i <= N; ++i) v[i][0] = i - p[i][0];    for (j = 1; j <= 18; ++j)        for (i = 1; i <= N; ++i)            if (p[i][j])                v[i][j] = v[i][j - 1] + v[p[i][j - 1]][j - 1] + (p[i][j - 1] - p[i][j]) * (1 << (j - 1));    int Q = read(), L, R, x;    while (Q--) {        L = read(), R = read(), x = read();        int P = cal(L, x) - cal(R + 1, x), q = R - L + 1;        int g = gcd(P, q);        printf("%d/%d\n", P / g, q / g);    }    return 0;}
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！