#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

const int maxn = 2e5 + 42;

int64_t ad[4 * maxn];
int64_t sm[4 * maxn];
int64_t px[4 * maxn];

void push(int v, int l, int r) {
	sm[v] += px[v] * ad[v];
	if(r - l > 1) {
		px[2 * v] += px[v];
		px[2 * v + 1] += px[v];
	}
	px[v] = 0;
}

void upd(int p, int64_t c, int v = 1, int l = 0, int r = maxn) {
	push(v, l, r);
	ad[v] += c;
	if(r - l > 1) {
		int m = (l + r) / 2;
		if(p < m) {
			upd(p, c, 2 * v, l, m);
		} else {
			upd(p, c, 2 * v + 1, m, r);
		}
	}
}

void add(int a, int b, int c, int v = 1, int l = 0, int r = maxn) {
	push(v, l, r);
	if(a <= l && r <= b) {
		px[v] += c;
		push(v, l, r);
	} else if(r <= a || b <= l) {
		return;
	} else {
		int m = (l + r) / 2;
		add(a, b, c, 2 * v, l, m);
		add(a, b, c, 2 * v + 1, m, r);
		sm[v] = sm[2 * v] + sm[2 * v + 1];
	}
}

int n;
vector<int> g[maxn];
vector<int> V;
int in[maxn], out[maxn], sz[maxn];
int t;

void dfs_sum(int v = 0, int p = 0, int h = 0) {
	in[v] = t++;
	sz[v] = 1;
	for(auto u: g[v]) {
		if(u != p) {
			dfs_sum(u, v, h + 1);
			add(in[u], out[u], 1);
			sz[v] += sz[u];
		}
	}
	upd(in[v], 1LL * V[v] * sz[v]);
	out[v] = t;
}

int64_t dfs(int v = 0, int p = 0) {
	int64_t res = sm[1];
	auto A = sm[1];
	upd(in[v], 1LL * V[v] * (n - 2 * sz[v] + 1));
	for(auto u: g[v]) {
		if(u != p) {
			add(in[u], out[u], -1);
			add(0, in[u], 1);
			add(out[u], n, 1);
			res = min(res, dfs(u, v));
			add(in[u], out[u], 1);
			add(0, in[u], -1);
			add(out[u], n, -1);
		}
	}
	upd(in[v], 1LL * V[v] * (2 * sz[v] - n - 1));
	assert(A == sm[1]);
	return res;
}

class RootItRight {
public:
	long long findMinimumTotalCost(int N, vector <int> edge, vector <int> val, int D, int seed, int MX) {
		n = N;
		vector<int> A(2 * N);
		A[0] = seed;
		for(int i = 1; i < 2 * N; i++) {
			A[i] = (A[i - 1] * 1103515245LL + 12345) % 2147483648LL;
		}
		auto E = edge;
		E.resize(N);
		for(int i = edge.size(); i < N; i++) {
			E[i] = (A[i] % min(i, D)) + i - min(i, D);
		}
		for(int i = 1; i < N; i++) {
			int u = i, v = E[i];
			g[u].push_back(v);
			g[v].push_back(u);
			
		}
		V = val;
		V.resize(N);
		for(int i = val.size(); i < N; i++) {
			V[i] = A[N + i] % MX;
		}
		dfs_sum();
		return dfs();
	}
} me;

void print(vector<int> x) {
	for(auto it: x) {
		cout << it << ' ';
	}
	cout << endl;
}

signed main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << me.findMinimumTotalCost(200000,
									{-1,0,0,0},
									{4,7},
									1,
									0,
									1000) << endl;
	return 0;
}