#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBhbGwoeCkgYmVnaW4oeCksIGVuZCh4KQoKY29uc3QgaW50IG1heG4gPSAyZTUgKyA0MjsKCmludDY0X3QgYWRbNCAqIG1heG5dOwppbnQ2NF90IHNtWzQgKiBtYXhuXTsKaW50NjRfdCBweFs0ICogbWF4bl07Cgp2b2lkIHB1c2goaW50IHYsIGludCBsLCBpbnQgcikgewoJc21bdl0gKz0gcHhbdl0gKiBhZFt2XTsKCWlmKHIgLSBsID4gMSkgewoJCXB4WzIgKiB2XSArPSBweFt2XTsKCQlweFsyICogdiArIDFdICs9IHB4W3ZdOwoJfQoJcHhbdl0gPSAwOwp9Cgp2b2lkIHVwZChpbnQgcCwgaW50NjRfdCBjLCBpbnQgdiA9IDEsIGludCBsID0gMCwgaW50IHIgPSBtYXhuKSB7CglwdXNoKHYsIGwsIHIpOwoJYWRbdl0gKz0gYzsKCWlmKHIgLSBsID4gMSkgewoJCWludCBtID0gKGwgKyByKSAvIDI7CgkJaWYocCA8IG0pIHsKCQkJdXBkKHAsIGMsIDIgKiB2LCBsLCBtKTsKCQl9IGVsc2UgewoJCQl1cGQocCwgYywgMiAqIHYgKyAxLCBtLCByKTsKCQl9Cgl9Cn0KCnZvaWQgYWRkKGludCBhLCBpbnQgYiwgaW50IGMsIGludCB2ID0gMSwgaW50IGwgPSAwLCBpbnQgciA9IG1heG4pIHsKCXB1c2godiwgbCwgcik7CglpZihhIDw9IGwgJiYgciA8PSBiKSB7CgkJcHhbdl0gKz0gYzsKCQlwdXNoKHYsIGwsIHIpOwoJfSBlbHNlIGlmKHIgPD0gYSB8fCBiIDw9IGwpIHsKCQlyZXR1cm47Cgl9IGVsc2UgewoJCWludCBtID0gKGwgKyByKSAvIDI7CgkJYWRkKGEsIGIsIGMsIDIgKiB2LCBsLCBtKTsKCQlhZGQoYSwgYiwgYywgMiAqIHYgKyAxLCBtLCByKTsKCQlzbVt2XSA9IHNtWzIgKiB2XSArIHNtWzIgKiB2ICsgMV07Cgl9Cn0KCmludCBuOwp2ZWN0b3I8aW50PiBnW21heG5dOwp2ZWN0b3I8aW50PiBWOwppbnQgaW5bbWF4bl0sIG91dFttYXhuXSwgc3pbbWF4bl07CmludCB0OwoKdm9pZCBkZnNfc3VtKGludCB2ID0gMCwgaW50IHAgPSAwLCBpbnQgaCA9IDApIHsKCWluW3ZdID0gdCsrOwoJc3pbdl0gPSAxOwoJZm9yKGF1dG8gdTogZ1t2XSkgewoJCWlmKHUgIT0gcCkgewoJCQlkZnNfc3VtKHUsIHYsIGggKyAxKTsKCQkJYWRkKGluW3VdLCBvdXRbdV0sIDEpOwoJCQlzelt2XSArPSBzelt1XTsKCQl9Cgl9Cgl1cGQoaW5bdl0sIDFMTCAqIFZbdl0gKiBzelt2XSk7CglvdXRbdl0gPSB0Owp9CgppbnQ2NF90IGRmcyhpbnQgdiA9IDAsIGludCBwID0gMCkgewoJaW50NjRfdCByZXMgPSBzbVsxXTsKCWF1dG8gQSA9IHNtWzFdOwoJdXBkKGluW3ZdLCAxTEwgKiBWW3ZdICogKG4gLSAyICogc3pbdl0gKyAxKSk7Cglmb3IoYXV0byB1OiBnW3ZdKSB7CgkJaWYodSAhPSBwKSB7CgkJCWFkZChpblt1XSwgb3V0W3VdLCAtMSk7CgkJCWFkZCgwLCBpblt1XSwgMSk7CgkJCWFkZChvdXRbdV0sIG4sIDEpOwoJCQlyZXMgPSBtaW4ocmVzLCBkZnModSwgdikpOwoJCQlhZGQoaW5bdV0sIG91dFt1XSwgMSk7CgkJCWFkZCgwLCBpblt1XSwgLTEpOwoJCQlhZGQob3V0W3VdLCBuLCAtMSk7CgkJfQoJfQoJdXBkKGluW3ZdLCAxTEwgKiBWW3ZdICogKDIgKiBzelt2XSAtIG4gLSAxKSk7Cglhc3NlcnQoQSA9PSBzbVsxXSk7CglyZXR1cm4gcmVzOwp9CgpjbGFzcyBSb290SXRSaWdodCB7CnB1YmxpYzoKCWxvbmcgbG9uZyBmaW5kTWluaW11bVRvdGFsQ29zdChpbnQgTiwgdmVjdG9yIDxpbnQ+IGVkZ2UsIHZlY3RvciA8aW50PiB2YWwsIGludCBELCBpbnQgc2VlZCwgaW50IE1YKSB7CgkJbiA9IE47CgkJdmVjdG9yPGludD4gQSgyICogTik7CgkJQVswXSA9IHNlZWQ7CgkJZm9yKGludCBpID0gMTsgaSA8IDIgKiBOOyBpKyspIHsKCQkJQVtpXSA9IChBW2kgLSAxXSAqIDExMDM1MTUyNDVMTCArIDEyMzQ1KSAlIDIxNDc0ODM2NDhMTDsKCQl9CgkJYXV0byBFID0gZWRnZTsKCQlFLnJlc2l6ZShOKTsKCQlmb3IoaW50IGkgPSBlZGdlLnNpemUoKTsgaSA8IE47IGkrKykgewoJCQlFW2ldID0gKEFbaV0gJSBtaW4oaSwgRCkpICsgaSAtIG1pbihpLCBEKTsKCQl9CgkJZm9yKGludCBpID0gMTsgaSA8IE47IGkrKykgewoJCQlpbnQgdSA9IGksIHYgPSBFW2ldOwoJCQlnW3VdLnB1c2hfYmFjayh2KTsKCQkJZ1t2XS5wdXNoX2JhY2sodSk7CgkJCQoJCX0KCQlWID0gdmFsOwoJCVYucmVzaXplKE4pOwoJCWZvcihpbnQgaSA9IHZhbC5zaXplKCk7IGkgPCBOOyBpKyspIHsKCQkJVltpXSA9IEFbTiArIGldICUgTVg7CgkJfQoJCWRmc19zdW0oKTsKCQlyZXR1cm4gZGZzKCk7Cgl9Cn0gbWU7Cgp2b2lkIHByaW50KHZlY3RvcjxpbnQ+IHgpIHsKCWZvcihhdXRvIGl0OiB4KSB7CgkJY291dCA8PCBpdCA8PCAnICc7Cgl9Cgljb3V0IDw8IGVuZGw7Cn0KCnNpZ25lZCBtYWluKCkgewoJLy9mcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKCWlvczo6c3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsKCWNvdXQgPDwgbWUuZmluZE1pbmltdW1Ub3RhbENvc3QoMjAwMDAwLAoJCQkJCQkJCQl7LTEsMCwwLDB9LAoJCQkJCQkJCQl7NCw3fSwKCQkJCQkJCQkJMSwKCQkJCQkJCQkJMCwKCQkJCQkJCQkJMTAwMCkgPDwgZW5kbDsKCXJldHVybiAwOwp9