#pragma region kyopro_template #define Nyaan_template #include #include #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template using V = vector; using vi = vector; using vl = vector; using vvi = vector>; using vd = V; using vs = V; using vvl = vector>; using P = pair; using vp = vector

; using pii = pair; using vpi = vector>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template void _cout(const pair &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template void _cout(const vector &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template void _cout(const vector> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template inline int getbit(T a, int i) { return (a >> i) & 1; } template inline void setbit(T &a, int i) { a |= (1LL << i); } template inline void delbit(T &a, int i) { a &= ~(1LL << i); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template int btw(T a, T x, T b) { return a <= x && x < b; } template T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template vector mkrui(const vector &v) { vector ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v) { vector inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; void solve(); int main() { solve(); } #pragma endregion using namespace std; template struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].eb(x, y, c); if (!is_directed) g[y].eb(y, x, c); } return g; } // Input of Edges template Edges esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template vector> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector> d(N, vector(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } using namespace std; template struct SegmentTree { int size; vector seg; const F func; const T UNIT; SegmentTree(int N, F func, T UNIT) : func(func), UNIT(UNIT) { size = 1; while (size < N) size <<= 1; seg.assign(2 * size, UNIT); } SegmentTree(const vector &v, F func, T UNIT) : func(func), UNIT(UNIT) { int N = (int)v.size(); size = 1; while (size < N) size <<= 1; seg.assign(2 * size, UNIT); for (int i = 0; i < N; i++) { seg[i + size] = v[i]; } build(); } void set(int k, T x) { seg[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { seg[k] = func(seg[2 * k], seg[2 * k + 1]); } } void update(int k, T x) { k += size; seg[k] = x; while (k >>= 1) { seg[k] = func(seg[2 * k], seg[2 * k + 1]); } } void add(int k, T x) { k += size; seg[k] += x; while (k >>= 1) { seg[k] = func(seg[2 * k], seg[2 * k + 1]); } } // query to [a, b) T query(int a, int b) { T L = UNIT, R = UNIT; for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) L = func(L, seg[a++]); if (b & 1) R = func(seg[--b], R); } return func(L, R); } T &operator[](const int &k) { return seg[k + size]; } template int find_subtree(int a, const C &check, T &M, bool type) { while (a < size) { T nxt = type ? func(seg[2 * a + type], M) : func(M, seg[2 * a + type]); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - size; } template int find_first(int a, const C &check) { T L = UNIT; if (a <= 0) { if (check(func(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = size; for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) { T nxt = func(L, seg[a]); if (check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template int find_last(int b, const C &check) { T R = UNIT; if (b >= size) { if (check(func(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = size; for (b += size; a < b; a >>= 1, b >>= 1) { if (b & 1) { T nxt = func(seg[--b], R); if (check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; void solve() { ini(N); vl a(N),b(N); in(a,b); auto g=graph(N); auto f=[&](ll a,ll b){return max(a,b);}; SegmentTree seg(N,f,-infLL); rep(i,N){ ll sc = a[i] - sz(g[i]) * b[i]; each(x, g[i]) sc -= b[x]; seg.set(i, sc); } seg.build(); ll ans = 0; rep(i,N) ans += b[i] * sz(g[i]); trc(ans); vi disp(N,0); while(seg.query(0,N) > 0) { rep(i,N)trc(i,seg.query(i,i+1)); ll ma = seg.query(0,N); ll ok = 0, ng = N; while(ok + 1 < ng) { ll m = (ok + ng) / 2; if(seg.query(ok,m) == ma) ng = m; else ok = m; } trc(ok); // okがアレ ans += ma; seg.update(ok, -infLL); disp[ok] = 1; each(x, g[ok]){ if(!disp[x]) seg.add(x, b[x]+b[ok]); } } trc(disp); out(ans); }