#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;
seg[i].mina=min(seg[i].mina,seg[i].aval+seg[i].asl);
seg[i].asl=inf;
return ;
}
seg[i].mina=min(seg[(i<<1)].mina+seg[(i<<1)].lazy,seg[(i<<1)^1].lazy+seg[(i<<1)^1].mina);
seg[i].mina=min(seg[i].mina,min(seg[(i<<1)].aval+seg[(i<<1)].asl,seg[(i<<1)^1].aval+seg[(i<<1)^1].asl));
}
void shift(long long i){
seg[i].vis=1;
if(i>=kaf){
return ;
}
seg[(i<<1)].vis=seg[(i<<1)^1].vis=1;
if(seg[i].lazy!=0){
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
}
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;
}
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=min(seg[i].asl,w);
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){
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,re);
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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 2 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 3 |
Correct |
24 ms |
71512 KB |
Output is correct |
| 4 |
Correct |
23 ms |
71516 KB |
Output is correct |
| 5 |
Correct |
22 ms |
71508 KB |
Output is correct |
| 6 |
Correct |
23 ms |
71512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
921 ms |
165788 KB |
Output is correct |
| 2 |
Correct |
708 ms |
170068 KB |
Output is correct |
| 3 |
Correct |
776 ms |
170368 KB |
Output is correct |
| 4 |
Correct |
894 ms |
179680 KB |
Output is correct |
| 5 |
Correct |
767 ms |
170048 KB |
Output is correct |
| 6 |
Correct |
822 ms |
169808 KB |
Output is correct |
| 7 |
Correct |
818 ms |
170064 KB |
Output is correct |
| 8 |
Correct |
751 ms |
170276 KB |
Output is correct |
| 9 |
Correct |
817 ms |
172364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
70220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 2 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 3 |
Correct |
24 ms |
71512 KB |
Output is correct |
| 4 |
Correct |
23 ms |
71516 KB |
Output is correct |
| 5 |
Correct |
22 ms |
71508 KB |
Output is correct |
| 6 |
Correct |
23 ms |
71512 KB |
Output is correct |
| 7 |
Incorrect |
12 ms |
70220 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 2 |
Correct |
22 ms |
71516 KB |
Output is correct |
| 3 |
Correct |
24 ms |
71512 KB |
Output is correct |
| 4 |
Correct |
23 ms |
71516 KB |
Output is correct |
| 5 |
Correct |
22 ms |
71508 KB |
Output is correct |
| 6 |
Correct |
23 ms |
71512 KB |
Output is correct |
| 7 |
Correct |
921 ms |
165788 KB |
Output is correct |
| 8 |
Correct |
708 ms |
170068 KB |
Output is correct |
| 9 |
Correct |
776 ms |
170368 KB |
Output is correct |
| 10 |
Correct |
894 ms |
179680 KB |
Output is correct |
| 11 |
Correct |
767 ms |
170048 KB |
Output is correct |
| 12 |
Correct |
822 ms |
169808 KB |
Output is correct |
| 13 |
Correct |
818 ms |
170064 KB |
Output is correct |
| 14 |
Correct |
751 ms |
170276 KB |
Output is correct |
| 15 |
Correct |
817 ms |
172364 KB |
Output is correct |
| 16 |
Incorrect |
12 ms |
70220 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
