| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1004588 | amirhoseinfar1385 | Nestabilnost (COI23_nestabilnost) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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();
}