#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 ] ;
for ( auto u: g[ v] ) {
if ( u ! = p) {
upd( in[ v] , 1LL * V[ v] * ( n - sz[ v] - sz[ u] ) ) ;
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] * ( sz[ v] + sz[ u] - n) ) ;
}
}
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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBhbGwoeCkgYmVnaW4oeCksIGVuZCh4KQoKY29uc3QgaW50IG1heG4gPSAyZTUgKyA0MjsKCmludDY0X3QgYWRbNCAqIG1heG5dOwppbnQ2NF90IHNtWzQgKiBtYXhuXTsKaW50NjRfdCBweFs0ICogbWF4bl07Cgp2b2lkIHB1c2goaW50IHYsIGludCBsLCBpbnQgcikgewoJc21bdl0gKz0gcHhbdl0gKiBhZFt2XTsKCWlmKHIgLSBsID4gMSkgewoJCXB4WzIgKiB2XSArPSBweFt2XTsKCQlweFsyICogdiArIDFdICs9IHB4W3ZdOwoJfQoJcHhbdl0gPSAwOwp9Cgp2b2lkIHVwZChpbnQgcCwgaW50NjRfdCBjLCBpbnQgdiA9IDEsIGludCBsID0gMCwgaW50IHIgPSBtYXhuKSB7CglwdXNoKHYsIGwsIHIpOwoJYWRbdl0gKz0gYzsKCWlmKHIgLSBsID4gMSkgewoJCWludCBtID0gKGwgKyByKSAvIDI7CgkJaWYocCA8IG0pIHsKCQkJdXBkKHAsIGMsIDIgKiB2LCBsLCBtKTsKCQl9IGVsc2UgewoJCQl1cGQocCwgYywgMiAqIHYgKyAxLCBtLCByKTsKCQl9Cgl9Cn0KCnZvaWQgYWRkKGludCBhLCBpbnQgYiwgaW50IGMsIGludCB2ID0gMSwgaW50IGwgPSAwLCBpbnQgciA9IG1heG4pIHsKCXB1c2godiwgbCwgcik7CglpZihhIDw9IGwgJiYgciA8PSBiKSB7CgkJcHhbdl0gKz0gYzsKCQlwdXNoKHYsIGwsIHIpOwoJfSBlbHNlIGlmKHIgPD0gYSB8fCBiIDw9IGwpIHsKCQlyZXR1cm47Cgl9IGVsc2UgewoJCWludCBtID0gKGwgKyByKSAvIDI7CgkJYWRkKGEsIGIsIGMsIDIgKiB2LCBsLCBtKTsKCQlhZGQoYSwgYiwgYywgMiAqIHYgKyAxLCBtLCByKTsKCQlzbVt2XSA9IHNtWzIgKiB2XSArIHNtWzIgKiB2ICsgMV07Cgl9Cn0KCmludCBuOwp2ZWN0b3I8aW50PiBnW21heG5dOwp2ZWN0b3I8aW50PiBWOwppbnQgaW5bbWF4bl0sIG91dFttYXhuXSwgc3pbbWF4bl07CmludCB0OwoKdm9pZCBkZnNfc3VtKGludCB2ID0gMCwgaW50IHAgPSAwLCBpbnQgaCA9IDApIHsKCWluW3ZdID0gdCsrOwoJc3pbdl0gPSAxOwoJZm9yKGF1dG8gdTogZ1t2XSkgewoJCWlmKHUgIT0gcCkgewoJCQlkZnNfc3VtKHUsIHYsIGggKyAxKTsKCQkJYWRkKGluW3VdLCBvdXRbdV0sIDEpOwoJCQlzelt2XSArPSBzelt1XTsKCQl9Cgl9Cgl1cGQoaW5bdl0sIDFMTCAqIFZbdl0gKiBzelt2XSk7CglvdXRbdl0gPSB0Owp9CgppbnQ2NF90IGRmcyhpbnQgdiA9IDAsIGludCBwID0gMCkgewoJaW50NjRfdCByZXMgPSBzbVsxXTsKCWZvcihhdXRvIHU6IGdbdl0pIHsKCQlpZih1ICE9IHApIHsKCQkJdXBkKGluW3ZdLCAxTEwgKiBWW3ZdICogKG4gLSBzelt2XSAtIHN6W3VdKSk7CgkJCWFkZChpblt1XSwgb3V0W3VdLCAtMSk7CgkJCWFkZCgwLCBpblt1XSwgMSk7CgkJCWFkZChvdXRbdV0sIG4sIDEpOwoJCQlyZXMgPSBtaW4ocmVzLCBkZnModSwgdikpOwoJCQlhZGQoaW5bdV0sIG91dFt1XSwgMSk7CgkJCWFkZCgwLCBpblt1XSwgLTEpOwoJCQlhZGQob3V0W3VdLCBuLCAtMSk7CgkJCXVwZChpblt2XSwgMUxMICogVlt2XSAqIChzelt2XSArIHN6W3VdIC0gbikpOwoJCX0KCX0KCXJldHVybiByZXM7Cn0KCmNsYXNzIFJvb3RJdFJpZ2h0IHsKcHVibGljOgoJbG9uZyBsb25nIGZpbmRNaW5pbXVtVG90YWxDb3N0KGludCBOLCB2ZWN0b3IgPGludD4gZWRnZSwgdmVjdG9yIDxpbnQ+IHZhbCwgaW50IEQsIGludCBzZWVkLCBpbnQgTVgpIHsKCQluID0gTjsKCQl2ZWN0b3I8aW50PiBBKDIgKiBOKTsKCQlBWzBdID0gc2VlZDsKCQlmb3IoaW50IGkgPSAxOyBpIDwgMiAqIE47IGkrKykgewoJCQlBW2ldID0gKEFbaSAtIDFdICogMTEwMzUxNTI0NUxMICsgMTIzNDUpICUgMjE0NzQ4MzY0OExMOwoJCX0KCQlhdXRvIEUgPSBlZGdlOwoJCUUucmVzaXplKE4pOwoJCWZvcihpbnQgaSA9IGVkZ2Uuc2l6ZSgpOyBpIDwgTjsgaSsrKSB7CgkJCUVbaV0gPSAoQVtpXSAlIG1pbihpLCBEKSkgKyBpIC0gbWluKGksIEQpOwoJCX0KCQlmb3IoaW50IGkgPSAxOyBpIDwgTjsgaSsrKSB7CgkJCWludCB1ID0gaSwgdiA9IEVbaV07CgkJCWdbdV0ucHVzaF9iYWNrKHYpOwoJCQlnW3ZdLnB1c2hfYmFjayh1KTsKCQkJCgkJfQoJCVYgPSB2YWw7CgkJVi5yZXNpemUoTik7CgkJZm9yKGludCBpID0gdmFsLnNpemUoKTsgaSA8IE47IGkrKykgewoJCQlWW2ldID0gQVtOICsgaV0gJSBNWDsKCQl9CgkJZGZzX3N1bSgpOwoJCXJldHVybiBkZnMoKTsKCX0KfSBtZTsKCnZvaWQgcHJpbnQodmVjdG9yPGludD4geCkgewoJZm9yKGF1dG8gaXQ6IHgpIHsKCQljb3V0IDw8IGl0IDw8ICcgJzsKCX0KCWNvdXQgPDwgZW5kbDsKfQ==