#include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 template struct dynamic_lazy_segtree { struct node{ int nxt[2]; S v; F lz; node(){ nxt[0] = -1; nxt[1] = -1; v = e(); lz = id(); } }; vector nodes; dynamic_lazy_segtree() : dynamic_lazy_segtree(0) {} dynamic_lazy_segtree(long long n){ log = 0; while((1LL< t(1,0); for(int i=log-1;i>=0;i--){ t.push_back(get(t.back(),(p>>i)&1)); } rep(i,t.size()-1){ push(t[i]); } reverse(t.begin(),t.end()); rep(i,t.size()){ if(i==0)nodes[t[i]].v = x; else{ update(t[i]); } } } S get(long long p) { assert(0 <= p && p < _n); int cur = 0; for(int i=log-1;i>=0;i--){ push(cur); cur = get(cur,(p>>i)&1); } return nodes[cur].v; } S prod(long long l,long long r,int cur,int depth){ if(cur==-1||r-l==0)return e(); if(r-l==(1LL<>(depth-1))&1){ l ^= 1LL<<(depth-1); r ^= 1LL<<(depth-1); return prod(l,r+1,nodes[cur].nxt[1],depth-1); } if(((r>>(depth-1))&1)==0){ return prod(l,r+1,nodes[cur].nxt[0],depth-1); } r ^= 1LL<<(depth-1); return op(prod(l,1LL<<(depth-1),nodes[cur].nxt[0],depth-1),prod(0,r+1,nodes[cur].nxt[1],depth-1)); } S prod(long long l, long long r) { assert(0 <= l && l <= r && r <= _n); return prod(l,r,0,log); } S all_prod() { return nodes[0].v; } void apply(long long p,F f){ assert(0 <= p && p < _n); vector t(1,0); for(int i=log-1;i>=0;i--){ t.push_back(get(t.back(),(p>>i)&1)); } rep(i,t.size()-1){ push(t[i]); } reverse(t.begin(),t.end()); rep(i,t.size()){ if(i==0)nodes[t[i]].v = mapping(f,nodes[t[i]].v); else{ update(t[i]); } } } void apply(long long l,long long r,int cur,int depth,F f){ if(r-l==0)return; if(r-l==(1LL<>(depth-1))&1){ l ^= 1LL<<(depth-1); r ^= 1LL<<(depth-1); apply(l,r+1,get(cur,1),depth-1,f); } else if(((r>>(depth-1))&1)==0){ apply(l,r+1,get(cur,0),depth-1,f); } else{ r ^= 1LL<<(depth-1); apply(l,1LL<<(depth-1),get(cur,0),depth-1,f); apply(0,r+1,get(cur,1),depth-1,f); } update(cur); return; } void apply(long long l,long long r,F f){ assert(0 <= l && l <= r && r <= _n); apply(l,r,0,log,f); } void update(int k){ nodes[k].v = e(); rep(i,2){ if(nodes[k].nxt[i]==-1)continue; nodes[k].v = op(nodes[k].v,nodes[nodes[k].nxt[i]].v); } } void all_apply(int k, F f) { nodes[k].v = mapping(f, nodes[k].v); nodes[k].lz = composition(f, nodes[k].lz); } void push(int k) { rep(i,2){ int t = get(k,i); all_apply(t,nodes[k].lz); } nodes[k].lz = id(); } long long _n,log; }; int N; vector> E; vector a; vector b; vector sz; long long op(long long a,long long b){ return max(a,b); } long long e(){ return 0; } long long mapping(long long a,long long b){ return a+b; } long long composition(long long a,long long b){ return a+b; } long long id(){ return 0; } using Segtree = dynamic_lazy_segtree; vector> ps; vector seg; void dfs0(int cur){ sz[cur] = 1; rep(i,E[cur].size()){ int to = E[cur][i]; dfs0(to); sz[cur] += sz[to]; } sort(E[cur].rbegin(),E[cur].rend(),[&](int a,int b){ return sz[a] pp; rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; for(auto j:ps[to]){ pp.push_back(j); } } pp.push_back(a[cur]); sort(pp.begin(),pp.end()); pp.erase(unique(pp.begin(),pp.end()),pp.end()); vector imos(pp.size(),0LL); rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; int d0 = -1; int d1; for(auto j:ps[to]){ d1 = distance(pp.begin(),lower_bound(pp.begin(),pp.end(),j)); long long v = seg[to].prod(j,N+1); imos[d1] += v; if(d0>=0)imos[d0] -= v; d0 = d1; } } for(int i=imos.size()-1;i>=1;i--){ imos[i-1] += imos[i]; } vector nv; rep(i,pp.size()){ long long D = imos[i]; int to = E[cur][0]; D += seg[to].prod(pp[i]+1,N+1); if(pp[i]==a[cur])D += b[cur]; nv.push_back(D); } swap(seg[cur],seg[E[cur][0]]); swap(ps[cur],ps[E[cur][0]]); rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; int d = 0; for(auto j:ps[to]){ long long v = seg[to].prod(j,N+1); seg[cur].apply(d,j,v); ps[cur].insert(j); d = j; } ps[to].clear(); seg[to] = dynamic_lazy_segtree(); } rep(i,pp.size()){ seg[cur].set(pp[i],nv[i]); } ps[cur].insert(a[cur]); } int main(){ cin>>N; E.resize(N); rep(i,N-1){ int p; scanf("%d",&p); p--; E[p].push_back(i+1); } a.resize(N); b.resize(N); rep(i,N){ scanf("%d",&a[i]); a[i]--; } rep(i,N)scanf("%lld",&b[i]); sz.resize(N); dfs0(0); seg.resize(N,dynamic_lazy_segtree(N+1)); ps.resize(N); dfs2(0); cout<