#include "tree.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
const int maxn = 2e5 + 5;

int n, dfn[maxn], siz[maxn], id[maxn], rk[maxn], cnt;
int f[18][maxn], h[18][maxn], w[maxn];
ll suf[maxn], val[maxn], suml;
vi g[maxn];

struct BIT
{
    int c[maxn];
    void add(int x, int d) { for (; x < maxn; x += (x & -x)) c[x] += d; }
    int sum(int x) { if (!x) return 0; int ans = 0; for (; x; x -= (x & -x)) ans += c[x]; return ans; }
    int que(int u) { return sum(dfn[u] + siz[u] - 1) - sum(dfn[u] - 1); }
}bit;

void dfs(int u)
{
    dfn[u] = ++cnt, siz[u] = 1;
    for (int v : g[u]) dfs(v), siz[u] += siz[v];
}

void init(vi P, vi W)
{
    n = P.size(); cnt = 0;
    for (int i = 1; i <= n; i++) bit.c[i] = 0;
    for (int i = 1; i <= n; i++) suf[i] = val[i] = 0, g[i].clear(); suml = 0;
    for (int i = 1; i <= n; i++)
    {
        id[i] = i, w[i] = W[i - 1], f[0][i] = P[i - 1] + 1;
        if (i > 1) g[P[i - 1] + 1].emplace_back(i);
    }
    sort(id + 1, id + n + 1, [&](int a, int b) { return w[a] < w[b]; }); dfs(1);
    for (int i = 1; i <= n; i++) rk[id[i]] = i;

    for (int i = 1; i <= n; i++) h[i][0] = rk[i];
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= n; i++)
            f[j][i] = f[j - 1][f[j - 1][i]], h[j][i] = min(h[j - 1][i], h[j - 1][f[j - 1][i]]);
    
    for (int i = 1; i <= n; i++) if (!g[i].size()) suml += w[i], bit.add(dfn[i], 1);
    for (int i = 1; i <= n; i++)
    {
        int u = id[i], nw = u;
        if (!g[u].size()) continue;
        for (int j = 17; ~j; j--) if (h[j][nw] >= i && rk[f[j][nw]] >= i) nw = f[j][nw];
        int x = bit.que(nw), y = bit.que(u) - 1;
        val[x] += w[u] - w[f[0][nw]]; val[x - y] -= w[u] - w[f[0][nw]];
        bit.add(dfn[u], -y); if (f[0][nw]) bit.add(dfn[f[0][nw]], y);
    }

    for (int i = n - 1; i; i--) val[i] += val[i + 1];
    suf[n + 1] = 0; for (int i = n; i; i--) suf[i] = suf[i + 1] + val[i];
}

ll query(int l, int r)
{
    int x = min(n + 1, (r / l) + 1);
    return val[x] * (r % l) + (suml + suf[x]) * l;
}