#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10,lg=19,kaf=(1<<lg);
vector<long long>adj[maxn];
long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
struct segment{
struct node{
long long mina,lazy,vis,aval,asl;
node(){
mina=0;
lazy=0;
vis=0;
aval=0;
asl=inf;
}
};
long long fen[maxn];
node seg[(1<<(lg+1))];
void ins(long long i,long long w){
seg[kaf+i].mina=w;
seg[kaf+i].aval=w;
fen[i]=w;
}
void build(){
for(long long i=kaf-1;i>=1;i--){
seg[i].mina=min(seg[(i<<1)].mina,seg[(i<<1)^1].mina);
seg[i].aval=seg[i].mina;
}
}
void calc(long long i){
seg[i].vis=1;
if(i>=kaf){
seg[i].mina+=seg[i].lazy;
seg[i].lazy=0;
return ;
}
seg[i].mina=min(seg[(i<<1)].mina+seg[(i<<1)].lazy,seg[(i<<1)^1].lazy+seg[(i<<1)^1].mina);
}
void calcasl(int i){
seg[i].vis=1;
if(i>=kaf){
seg[i].mina+=seg[i].lazy;
seg[i].lazy=0;
seg[i].mina=min(seg[i].mina,seg[i].asl+seg[i].aval);
seg[i].asl=inf;
return ;
}
seg[(i<<1)].vis=seg[(i<<1)^1].vis=1;
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
calc(i);
seg[i].mina=min(seg[i].mina,seg[i].asl+seg[i].aval);
}
void shift(long long i){
if(seg[i].asl==inf){
seg[i].vis=1;
if(i>=kaf){
return ;
}
seg[(i<<1)].vis=seg[(i<<1)^1].vis=1;
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
calc(i);
}else{
seg[i].vis=seg[(i<<1)].vis=seg[(i<<1)^1].vis=1;
seg[(i<<1)].asl=min(seg[(i<<1)].asl,seg[i].asl);
seg[(i<<1)^1].asl=min(seg[(i<<1)^1].asl,seg[i].asl);
seg[i].asl=inf;
calcasl((i<<1));
calcasl((i<<1)^1);
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
calc(i);
}
}
void push(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
shift(i);
calc(i);
seg[i].asl=w;
calcasl(i);
shift(i);
calc(i);
return ;
}
shift(i);
long long m=(l+r)>>1;
push((i<<1),l,m,tl,tr,w);
push((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
}
void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
shift(i);
calc(i);
seg[i].lazy+=w;
shift(i);
calc(i);
return ;
}
shift(i);
long long m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
}
long long getmin(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return inf;
}
shift(i);
calc(i);
if(l>=tl&&r<=tr){
return seg[i].mina+seg[i].lazy;
}
long long m=(l+r)>>1;
return min(getmin((i<<1),l,m,tl,tr),getmin((i<<1)^1,m+1,r,tl,tr));
}
void clear(long long i=1,int l=0,int r=kaf-1,int tl=1,int tr=n+10){
if(l>r||l>tr||r<tl||tl>tr||seg[i].vis==0){
return ;
}
if(l>=tl&&r<=tr){
seg[i].vis=0;
seg[i].mina=seg[i].aval;
seg[i].lazy=0;
seg[i].asl=inf;
}else{
shift(i);
}
if(l==r){
if(!(l>=tl&&r<=tr)){
calc(i);
}
return ;
}
int m=(l+r)>>1;
clear((i<<1),l,m,tl,tr);
clear((i<<1)^1,m+1,r,tl,tr);
if(!(l>=tl&&r<=tr)){
calc(i);
}
}
}seg;
bool cmp(long long a,long long b){
return sz[a]>sz[b];
}
void predfs(long long u,long long par=-1){
if(par!=-1){
sort(adj[u].begin(),adj[u].end());
adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
}
sz[u]=1;
for(auto x:adj[u]){
predfs(x,u);
sz[u]+=sz[x];
}
sort(adj[u].begin(),adj[u].end(),cmp);
}
void vorod(){
cin>>n;
for(long long i=1;i<=n;i++){
cin>>all[i];
}
for(long long i=1;i<=n;i++){
cin>>wa[i];
}
for(long long i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void pre(){
predfs(1);
for(long long i=1;i<=n;i++){
seg.ins(i,wa[i]);
}
seg.build();
}
set<long long>allind[maxn];
long long mainres=0;
long long dfs(long long u){
long long ret=0;
vector<pair<pair<long long,long long>,long long>>alle;
for(long long i=1;i<(long long)adj[u].size();i++){
long long v=adj[u][i];
long long re=dfs(v);
if(all[v]!=0&&all[v]-1!=all[u]){
mainres+=re;
seg.clear();
continue;
}
allind[v].insert(all[u]+1);
allind[v].insert(all[u]+2);
allind[v].insert(1);
deque<long long>tof;
for(auto x:allind[v]){
tof.push_back(x);
}
tof.push_back(n+1);
if(all[v]==all[u]+1){
seg.upd(1,0,kaf-1,1,all[v],inf2);
}else{
seg.upd(1,0,kaf-1,1,all[u],inf2);
seg.upd(1,0,kaf-1,all[u]+2,n,inf2);
}
for(long long i=0;i<(long long)tof.size()-1;i++){
if(tof[i+1]==tof[i]){
continue;
}
long long w=seg.getmin(1,0,kaf-1,tof[i],tof[i])-wa[tof[i]];
w=min(re,w);
if(tof[i]<=all[v]){
w=re;
}
alle.push_back(make_pair(make_pair(tof[i],tof[i+1]-1),w));
}
seg.clear();
}
if((int)adj[u].size()==0){
return seg.getmin(1,0,kaf-1,all[u]+1,n);
}
long long v=adj[u][0];
long long re=dfs(v);
//wrf:
//for(int i=1;i<=n;i++){
// if(seg.fen[i]>re+wa[i]){
// seg.fen[i]=re+wa[i];
// }
//}
seg.push(1,0,kaf-1,1,n);
if(all[v]!=0&&all[v]-1!=all[u]){
mainres+=re;
seg.clear();
}else{
swap(allind[u],allind[v]);
allind[u].insert(all[u]+1);
allind[u].insert(all[u]+2);
if(all[v]==all[u]+1){
seg.clear(1,0,kaf-1,1,all[v]);
seg.upd(1,0,kaf-1,1,all[v],re);
}else{
seg.clear(1,0,kaf-1,1,all[u]);
seg.clear(1,0,kaf-1,all[u]+2,n);
seg.upd(1,0,kaf-1,1,all[u],re);
seg.upd(1,0,kaf-1,all[u]+2,n,re);
}
}
for(auto x:alle){
allind[u].insert(x.first.first);
allind[u].insert(x.first.second+1);
seg.upd(1,0,kaf-1,x.first.first,x.first.second,x.second);
}
ret+=seg.getmin(1,0,kaf-1,all[u]+1,n);
return ret;
}
void solve(){
mainres+=dfs(1);
cout<<mainres<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vorod();
pre();
solve();
}
Compilation message
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:248:24: error: no matching function for call to 'segment::push(int, int, long long int, int, long long int&)'
248 | seg.push(1,0,kaf-1,1,n);
| ^
code1.cpp:80:7: note: candidate: 'void segment::push(long long int, long long int, long long int, long long int, long long int, long long int)'
80 | void push(long long i,long long l,long long r,long long tl,long long tr,long long w){
| ^~~~
code1.cpp:80:7: note: candidate expects 6 arguments, 5 provided
