| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1004636 | amirhoseinfar1385 | Nestabilnost (COI23_nestabilnost) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 j=tl;j<=tr;j++){
fen[j]+=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(tl>tr){
return inf;
}
long long mn=fen[tl];
for(int j=tl+1;j<=tr;j++){
mn=min(mn,fen[j]);
}
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 j=tl;j<=tr;j++){
fen[j]=wa[j];
}
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){
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;
}
for(int i=1;i<=n;i++){
if(seg.gemin(1,0,kaf-1,i,i)-wa[i]>=re){
allind[u].insert(i);
}
}
if(all[v]==all[u]+1){
allind[v].insert(all[v]+1);
allind[v].insert(all[v]);
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){
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.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=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];
}
}
if(all[v]!=0&&all[v]-1!=all[u]){
mainres+=re;
seg.clear();
}else{
swap(allind[u],allind[v]);
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);
allind[u].insert(all[v]);
allind[u].insert(all[v]-1);
}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].insert(all[u]+1);
allind[u].insert(all[u]+2);
}
}
for(auto x:alle){
allind[u].insert(x.first.first);
allind[u].insert(x.first.first-1);
allind[u].insert(x.first.first+1);
allind[u].insert(x.first.second);
allind[u].insert(x.first.second+2);
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();
}