#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 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 = 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] &t){ if(t.size()==0){ queue Q; Q.push(cur); t.push_back(N); while(Q.size()>0){ int u = Q.front(); Q.pop(); t.push_back(a[u]); rep(i,E[u].size()){ int to = E[u][i]; Q.push(to); } } sort(t.begin(),t.end()); } rep(i,E[cur].size()){ int to = E[cur][i]; if(i==0){ dfs1(to,t); } else{ t.resize(0); dfs1(to,t); } } if(E[cur].size()==0){ ps[cur] = t; seg[cur] = Segtree(t.size()); } } void dfs2(int cur){ if(E[cur].size()==0){ int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),a[cur])); seg[cur].set(d,b[cur]); seg[cur].set(ps[cur].size()-1,0); return; } if(E[cur].size()==1){ int to = E[cur][0]; dfs2(to); swap(ps[cur],ps[to]); swap(seg[cur],seg[to]); int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),a[cur])); seg[cur].set(d,seg[cur].prod(d+1,ps[cur].size())+b[cur]); return; } rep(i,E[cur].size()){ int to = E[cur][i]; dfs2(to); } vector pp; rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; rep(j,ps[to].size()){ pp.push_back(ps[to][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]; rep(j,ps[to].size()){ int d0; if(j!=0)d0 = distance(pp.begin(),lower_bound(pp.begin(),pp.end(),ps[to][j-1])); else d0 = -1; int d1 = distance(pp.begin(),lower_bound(pp.begin(),pp.end(),ps[to][j])); long long v = seg[to].prod(j,ps[to].size()); imos[d1] += v; if(d0>=0)imos[d0] -= v; } } 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]; int d = distance(ps[to].begin(),upper_bound(ps[to].begin(),ps[to].end(),pp[i])); D += seg[to].prod(d,ps[to].size()); 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]; rep(j,ps[to].size()){ int d0; if(j!=0) d0 = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),ps[to][j-1])); else d0 = 0; int d1 = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),ps[to][j])); long long v = seg[to].prod(j,ps[to].size()); seg[cur].apply(d0,d1,v); } } rep(i,pp.size()){ int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),pp[i])); seg[cur].set(d,nv[i]); } } 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); ps.resize(N); vector t; dfs1(0,t); dfs2(0); cout<