#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; struct Data{ long long v = 0;; bool f = false; }; Data op(Data a,Data b){ if(a.f==false)return b; if(b.f==false)return a; if(a.v>b.v)return a; return b; } Data e(){ return Data(); } Data mapping(long long a,Data b){ if(b.f)b.v += a; return 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],true}); seg[cur].set(ps[cur].size()-1,{0,true}); 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()).v+b[cur],true}); 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()).v; 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()).v; if(pp[i]==a[cur])D += b[cur]; nv.push_back(D); } /* cout<>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]); //cout<<'a'< t; dfs1(0,t); //cout<<'a'<