#include "tree.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

typedef long long ll;

using namespace std;

const int MAXN = 2e5 + 10;

int n, fa[MAXN], wt[MAXN];
vector <int> e[MAXN];

int dfn[MAXN], clk = -1, sz[MAXN];
void DFS1(int u)
{
	dfn[u] = ++clk, sz[u] = 1;
	for (auto v : e[u]) DFS1(v), sz[u] += sz[v];
}

struct BIT
{
	int bit[MAXN];
	inline void Add(int x, int k) { for (; x <= n; x += (x & -x)) bit[x] += k; }
	inline int Ask(int x) { int res = 0; for (; x; x -= (x & -x)) res += bit[x]; return res; }
	inline int Ask(int l, int r) { return Ask(r) - Ask(l - 1); }
}bt;

struct DSU
{
	int fa[MAXN], lst[MAXN];
	int Find(int k)
	{
		if (k == fa[k]) return k;
		int t = Find(fa[k]);
		if (t == fa[k]) lst[k] = k;
		else lst[k] = lst[fa[k]];
		return fa[k] = t;
	}
}U;

int id[MAXN], top[MAXN];
ll f[MAXN], leaf;

void init(vector <int> P, vector <int> W)
{
	n = P.size();
	for (int i = 0; i < n; i++) fa[i + 1] = P[i] + 1;
	for (int i = 0; i < n; i++) wt[i + 1] = W[i];
	for (int i = 1; i <= n; i++) e[fa[i]].push_back(i);
	DFS1(0);
	iota(id + 1, id + n + 1, 1);
	sort(id + 1, id + n + 1, [&](int x, int y) { return wt[x] > wt[y]; });
	for (int i = 1; i <= n; i++) U.fa[i] = i;
	for (int i = 1; i <= n; i++)
	{
		int u = id[i];
		if (!e[u].size()) continue;
		U.fa[u] = fa[u]; U.Find(u), top[u] = U.lst[u];
	}
	for (int i = 1; i <= n; i++)
		if (!e[i].size()) bt.Add(dfn[i], 1), leaf += wt[i];
	for (int i = n; i >= 1; i--)
	{
		int u = id[i];
		if (!e[u].size()) continue;
		int x = bt.Ask(dfn[top[u]], dfn[top[u]] + sz[top[u]] - 1), y = bt.Ask(dfn[u], dfn[u] + sz[u] - 1) - 1, z = wt[u] - wt[fa[top[u]]];
		// cout << u << ' ' << x << ' ' << y << ' ' << z << '\n';
		f[x] += z, f[x - y] -= z;
		bt.Add(dfn[u], -y);
		if (fa[top[u]]) bt.Add(dfn[fa[top[u]]], y);
	}
	for (int i = n - 1; i; i--) f[i] += f[i + 1];
	for (int i = n - 1; i; i--) f[i] += f[i + 1];
	// for (int i = 1; i <= n; i++) cout << f[i] << ' '; cout << '\n';
}

ll query(int l, int r)
{
	int x = min(n + 1, r / l + 1);
	return (f[x] + leaf) * l - (f[x] - f[x + 1]) * (r % l);
}