#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } class Scc{ public: int N; vector> G; vector> G_inv; vector idx; Scc(int n){ N = n; G = vector>(n, vector()); G_inv = vector>(n, vector()); used = vector(n, false); idx = vector(n); } void add_edge(int from, int to){ G[from].push_back(to); G_inv[to].push_back(from); } vector> scc(){ vector> ans; for(int i = 0; i < N; i++){ if(!used[i]) dfs1(i); } clear(); int cur = 0; for(int i = vs.size()-1; i >= 0; i--){ if(!used[vs[i]]) { dfs2(vs[i], cur); cur++; ans.push_back(buf); buf.clear(); } } return ans; } private: vector used; vector vs; vector buf; void clear(){ for(int i = 0; i < N; i++) used[i] = false; } void dfs1(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]) dfs1(G[v][i]); } vs.push_back(v); } void dfs2(int v, int k){ used[v] = true; idx[v] = k; for(int i = 0; i < G_inv[v].size(); i++){ if(!used[G_inv[v][i]]) dfs2(G_inv[v][i], k); } buf.push_back(v); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n; cin >> n; vector a(n), b(n); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; atcoder::scc_graph scc(n); vector c(n); for(int i = 0; i < n; i++){ cin >> c[i]; c[i]--; scc.add_edge(c[i], i); // scc.add_edge(i, c); } auto components = scc.scc(); int m = components.size(); vector aa(m), bb(m); vector idx(n); for(int i = 0; i < m; i++){ for(int v: components[i]){ aa[i] += a[v]; bb[i] += b[v]; idx[v] = i; } print_vector(components[i]); } print_vector(idx); vector> g(m); vector> g_inv(m); for(int i = 0; i < n; i++){ if(idx[i] != idx[c[i]]){ // cout << "===" << endl; // cout << c[i] << ' ' << i << endl; // print_vector(components[idx[c[i]]]); // print_vector(components[idx[i]]); // cout << idx[c[i]] << "->" << idx[i] << endl; assert(idx[c[i]] < idx[i]); g[idx[c[i]]].push_back(idx[i]); g_inv[idx[i]].push_back(idx[c[i]]); } } ll a_sum = accumulate(a.begin(), a.end(), 0ll); ll b_sum = accumulate(b.begin(), b.end(), 0ll); auto ok = [&](ll x){ if(x > a_sum/b_sum) return false; vector req(m); for(int i = 0; i < m; i++) req[i] = bb[i]*x; // cout << "=====" << endl; // cout << x << endl; // print_vector(aa); // print_vector(req); for(int i = m-1; i >= 0; i--){ if(req[i] <= aa[i]){ }else{ // 不足している if(g_inv[i].empty()) return false; int par = g_inv[i][0]; req[par] += req[i]-aa[i]; } } return true; }; ll l = 0, r = a_sum/b_sum+1; while(r-l > 1){ ll x = (l+r)/2; if(ok(x)) l = x; else r = x; } cout << l << endl; }