#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;
node(){
mina=0;
lazy=0;
vis=0;
aval=0;
}
};
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 shift(long long i){
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;
}
void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
for(int i=l;i<=r;i++){
fen[i]+=w;
}
return ;
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
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){
return inf;
}
int mn=fen[l];
for(int i=l+1;i<=r;i++){
mn=min(mn,fen[i]);
}
return mn;
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){
for(int i=l;i<=r;i++){
fen[i]=wa[i];
}
return ;
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;
}
if(l==r){
return ;
}
int m=(l+r)>>1;
clear((i<<1),l,m,tl,tr);
clear((i<<1)^1,m+1,r,tl,tr);
}
}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){
// adj[u].erase(find(adj[u].begin(),adj[u].end(),par));
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){
//cout<<u<<endl;
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;
continue;
}
ret+=re;
if(all[v]==all[u]+1){
allind[v].insert(all[v]+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){
while(tof.front()<=all[v]){
tof.pop_front();
}
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);
tof.clear();
tof.push_back(all[u]+1);
tof.push_back(all[u]+2);
}
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-=re;
if(w>=0){
continue;
}
alle.push_back(make_pair(make_pair(tof[i],tof[i+1]-1),w));
}
seg.clear();
}
//cout<<"ha: "<<u<<endl;
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);
//cout<<"bar: "<<u<<endl;
if(all[v]!=0&&all[v]-1!=all[u]){
mainres+=re;
seg.clear();
}else{
swap(allind[u],allind[v]);
// ret+=re;
// if(u==5){
// //cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl;
// }
// seg.upd(1,0,kaf-1,1,n,-re);
// if(u==5){
// //cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl;
// }
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);
allind[u].insert(all[v]+1);
while((*allind[u].begin())<=all[v]){
allind[u].erase((*allind[u].begin()));
}
}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);
allind[u].clear();
allind[u].insert(all[u]+1);
allind[u].insert(all[u]+2);
}
}
//cout<<"hey1: "<<seg.getmin(1,0,kaf-1,1,3)<<endl;
for(auto x:alle){
allind[u].insert(x.first.first);
seg.upd(1,0,kaf-1,x.first.first,x.first.second,x.second);
// if(u==1){
//cout<<"chy: "<<x.first.first<<" "<<x.first.second<<" "<<x.second<<endl;
// }
}
//cout<<"hey2: "<<seg.getmin(1,0,kaf-1,1,3)<<endl;
//cout<<"ghablret: "<<ret<<endl;
ret+=seg.getmin(1,0,kaf-1,all[u]+1,n);
//cout<<"ret: "<<u<<" "<<ret<<endl;
return ret;
}
void solve(){
mainres+=dfs(1);
cout<<mainres<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
vorod();
pre();
solve();
}
Compilation message
code1.cpp: In member function 'long long int segment::getmin(long long int, long long int, long long int, long long int, long long int)':
code1.cpp:75:20: error: no matching function for call to 'min(int&, long long int&)'
75 | mn=min(mn,fen[i]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from code1.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
code1.cpp:75:20: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
75 | mn=min(mn,fen[i]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from code1.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
code1.cpp:75:20: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
75 | mn=min(mn,fen[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from code1.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
code1.cpp:75:20: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
75 | mn=min(mn,fen[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from code1.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
code1.cpp:75:20: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
75 | mn=min(mn,fen[i]);
| ^
