我觉得很毒瘤了，真是一场酣畅淋漓的 3000 大战。

题意简述：

给定 $n$ 个点的有根树，根为 $1$，点 $i$ 的父亲为 $p_i$。

每个节点 $i$ 有一个对应区间 $[l_i,r_i]$，表示可以给该点设置一个正整数权值 $w_i\in[l_i,r_i]$。

$m$ 组询问，每组询问给定 $(a,b)$ 和 $(c,d)$，表示在该次询问中路径 $a\to b$ 和 $c\to d$ 上的节点权值必须两两相同。保证两路径长度相等。

对于每个 $i\in[1,m]$，求满足前 $i$ 个询问限制下决定权值的方案数。

重要发言：对于一个单 log 和双 log 都能过的题，两只 log 的写法一般比单只 log 的写法可爱。

秉承着可爱即正义的原则是不可能写单 log 的写法的。

单 log 正解已在 CF1801E 的题解区 有详解。

你可能需要用的：DSU / HLD / BIT。

首先询问是累计的，所以之前的相等限制不会改变。

维护相等关系，使用并查集。

每次分别遍历两条路径，合并要求相等的节点；若干个要求相等的节点构成一个等价类，则该等价类所有结点的取值为 $[\max l_i,\min r_i]$。

即一个等价类中所有节点下限的最大值到上限的最小值都在可接受范围内，贡献为 $\min r_i-\max l_i + 1$，当然如果 $\max l_i>\min r_i$ 则贡献为 $0$。

对于每个等价类都维护这个东西，每次合并的时候将已有的答案先去除两个原有等价类的贡献，再加上合并后等价类的贡献即可。

时间复杂度 $\mathcal{O}(nm\alpha(n))$，不可过（后文复杂度默认省去 $\alpha(n)$）。

并查集的复杂度显然不能优化，从遍历路径入手，考虑如何优化寻找待合并节点的过程。

当两条路径上的所有对应节点都在相同等价类中时，这个时候再对每个节点依次合并是无用的；就算有还未合并的节点，也没有必要遍历一遍整个路径，需要通过一种跳跃的方式，在能够快速判断一段路径是否满足「对应节点都位于相同等价类」的前提下快速的跳至需合并的位置。

讲到这份上了可能就看得出来上个树剖 & 哈希就是对的。

剖一下，对于每个等价类设置一个唯一权值（比如 root 编号），做进制哈希即可（据说 base 不能设 131 XD）。

查询一段路径的哈希就结合树剖使用树状数组维护，注意分正反，反着的 reverse 一下。

合并等价类的时候同样需要修改对应哈希值。

Tips：哈希的判定区间要求是等长的，挂了会过不去样例 /ll。

最后在已处理好的若干区间内寻找待合并的等价类即可，暴力查找会炸掉，二分。

总复杂度 $\mathcal{O}(n\log^2 n)$，即获取路径拆分后的区间 & 二分时查询树状数组值，该两部分的复杂度一致，其余部分常数影响。

代码如下。

没卡常，关了同步流勉强跑进最优解第一页（当前）。

巨大 5.8k 写法，码量还是完输单 log 写法的【擦汗】。

#include <bits/stdc++.h>
#define break ({break;})
#define continue ({continue;})
#define return(kafu) ({return kafu;})

#define lc first
#define rc second

using namespace std;
typedef long long i64;
typedef double f16;
typedef pair <int, int> pii;

const int N = 2e5 + 10, P = 1e9 + 7, base = 2177;
int fa[N], siz[N], hev[N], top[N], dfn[N], dcnt, i2d[N];
i64 pov[N], nev[N], ans = 1;
int n, m, l[N], r[N];
vector <int> g[N], eq[N];

i64 qpow (i64 b, int e)
{
    i64 res = 1;
    while (e)
    {
        if (e & 1) res = res * b % P;
        b = b * b % P;
        e >>= 1;
    }
    return res % P;
}
#define inv(x) qpow (x, P - 2)
#define sub(x,y) ((x - y + P) % P)

struct FWAp
{
    i64 v[N]; FWAp () { memset (v, 0, sizeof (v)); }
    int lowbit (int x) { return x & (-x); }
    void modify (int u, i64 c) { for (; u <= n; u += lowbit (u)) v[u] = (v[u] + c) % P; }
    i64 query (int u) { i64 res = 0; for (; u; u -= lowbit (u)) res = (res + v[u]) % P; return res; }
}; FWAp fp;

struct FWAn
{
	i64 v[N]; FWAn () { memset (v, 0, sizeof (v)); }
    int lowbit (int x) { return x & (-x); }
    void modify (int u, i64 c) { for (; u; u -= lowbit (u)) v[u] = (v[u] + c) % P; }
    i64 query (int u) { i64 res = 0; for (; u <= n; u += lowbit (u)) res = (res + v[u]) % P; return res; }
}; FWAn fn;

struct DSU
{
    int fa[N]; void clear () { for (int i = 1; i < N; i ++) fa[i] = i; } DSU () { clear (); }
    int find (int u) { return (fa[u] == u ? u : fa[u] = find (fa[u])); }
    
    void merge (int u, int v)
    {
        u = find (u), v = find (v);
        if (u == v) return;
        if (eq[u].size () < eq[v].size ()) swap (u, v);

        if (l[u] <= r[u]) ans = ans * inv (r[u] - l[u] + 1) % P; else ans = 0;
        if (l[v] <= r[v]) ans = ans * inv (r[v] - l[v] + 1) % P; else ans = 0;
        l[u] = max (l[u], l[v]), r[u] = min (r[u], r[v]);
        if (l[u] <= r[u]) ans = ans * (r[u] - l[u] + 1) % P; else ans = 0;

        fa[v] = u;
        for (int i : eq[v])
        {
            eq[u].push_back (i);
            fp.modify (dfn[i], pov[dfn[i] - 1] * sub (u, v) % P);
            fn.modify (dfn[i], pov[n - dfn[i]] * sub (u, v) % P);
        }
    }
}; DSU dsu;

void fac_init (int n)
{
    pov[0] = 1;
    for (int i = 1; i <= n; i ++) pov[i] = pov[i - 1] * base % P;
    nev[n] = inv (pov[n]);
    for (int i = n - 1; i >= 0; i --) nev[i] = nev[i + 1] * base % P;
}
#define val_p(l,r) (nev[l - 1] * sub (fp.query (r), fp.query (l - 1)) % P)
#define val_n(l,r) (nev[n - r] * sub (fn.query (l), fn.query (r + 1)) % P)
#define chkval(l,r) (l <= r ? val_p (l, r) : val_n (r, l))

void DFS0 (int u, int f)
{
    fa[u] = f, siz[u] = 1;
    for (int v : g[u])
    {
        if (v == f) continue;
        DFS0 (v, u), siz[u] += siz[v];
        if (siz[v] > siz[hev[u]]) hev[u] = v;
    }
}

void DFS1 (int u, int f)
{
    dfn[u] = ++ dcnt;
    if (hev[u]) top[hev[u]] = top[u], DFS1 (hev[u], u);
    for (int v : g[u])
    {
        if (v == f || v == hev[u]) continue;
        top[v] = v, DFS1 (v, u);
    }
}

int LCA (int u, int v)
{
    while (top[u] != top[v])
    {
        if (dfn[u] < dfn[v]) swap (u, v);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) swap (u, v);
    return u;
}

vector <pii> sec, has[2]; // 0:p 1:n
void proc_sec (int u, int v, int tp, int c)
{
    sec.clear ();
    while (top[u] != top[v])
    {
        if (dfn[u] < dfn[v]) swap (u, v);
        if (!tp) sec.push_back ({dfn[u], dfn[top[u]]});
        else sec.push_back ({dfn[top[u]], dfn[u]});
        u = fa[top[u]];
    }
    if (!tp) sec.push_back ({dfn[u], dfn[v]});
    else
    {
        if (dfn[u] != dfn[v]) sec.push_back ({dfn[v] + 1, dfn[u]});
        reverse (sec.begin (), sec.end ());
    }
    for (pii i : sec) has[c].push_back (i);
}

vector <pii> ssec[2];
#define len(i) (abs (i.rc - i.lc) + 1)
#define jud(i) (i.lc <= i.rc ? 1 : -1)
#define iden(p,i) (p.lc + jud (p) * (i - 1))
void adjust (int c)
{
    int l = 0, r = 0, pos = 0;
    for (pii p : has[c])
    {
        int last = p.lc;
        while (r + len (has[!c][pos]) <= l + len (p) && pos < has[!c].size ())
        {
            r += len (has[!c][pos]);
            ssec[c].push_back ({last, p.lc + (r - l - 1) * jud (p)});
            last = p.lc + (r - l) * jud (p), pos ++;
        }
        if (last * jud (p) <= p.rc * jud (p)) ssec[c].push_back ({last, p.rc});
        l += len (p);
    }
}

int main ()
{
	cin.tie (0) -> sync_with_stdio (0);
    cin >> n;
    fac_init (N - 1);
    for (int i = 2, f; i <= n; i ++)
        cin >> f, g[f].push_back (i), g[i].push_back (f);
    for (int i = 1; i <= n; i ++)
        cin >> l[i] >> r[i], ans = ans * (r[i] - l[i] + 1) % P;
    for (int i = 1; i <= n; i ++) eq[i].push_back (i);
    
    top[1] = 1, DFS0 (1, 0), DFS1 (1, 0);
    for (int i = 1; i <= n; i ++) i2d[dfn[i]] = i;
    for (int i = 1; i <= n; i ++)
        fp.modify (dfn[i], pov[dfn[i] - 1] * i % P), fn.modify (dfn[i], pov[n - dfn[i]] * i % P);
    
    cin >> m;
    while (m --)
    {
        int u0, v0, u1, v1; cin >> u0 >> v0 >> u1 >> v1;
        int f0 = LCA (u0, v0), f1 = LCA (u1, v1);
        for (int i = 0; i < 2; i ++) has[i].clear (), ssec[i].clear ();
        proc_sec (u0, f0, 0, 0), proc_sec (v0, f0, 1, 0);
        proc_sec (u1, f1, 0, 1), proc_sec (v1, f1, 1, 1);
        adjust (0), adjust (1);
        
        for (int i = 0; i < ssec[0].size (); i ++)
        {
            int l = 0, r = 0;
            while (chkval (ssec[0][i].lc, ssec[0][i].rc) != chkval (ssec[1][i].lc, ssec[1][i].rc))
            {
                l ++, r = len (ssec[0][i]);
                while (l < r)
                {
                    int mid = (l + r) >> 1;
                    if (chkval (ssec[0][i].lc, iden (ssec[0][i], mid)) != chkval (ssec[1][i].lc, iden (ssec[1][i], mid)))
                        r = mid;
                    else l = mid + 1;
                }
				dsu.merge (i2d[iden (ssec[0][i], l)], i2d[iden (ssec[1][i], l)]);
			}
        }
        
        cout << ans << '\n';
    }
    return 0;
}