P4338 [zjoi2018] history (tree section) (violence)

Preface

A little annoyed …
There are no other ones ZJOI So cancer , See the key conclusion , But in the end, the maintenance is stuck log The parachutist nature of this imaginary edge is .

analysis

At first sight ： I don't think I can do it at all .
Calm down , Since it is still abnormal with repair , It must be something that can be transformed into something more formal .
For each node, consider how many times you contributed to the answer , set up $s_x$ Express x Sum of weights in subtree ,$m{x}_x$ Express $\max (a_x,{\max }_{u\in so{n}_x}{s}_u)$, So the upper bound of the answer is obviously $s_x-1$, But the premise is that the weights of different subtrees must be staggered , So it should be $\min (s_x-1,2(s_x-m{x}_x))$, Recursively, you can find that this conclusion is always right . Write a violent get 30 branch , Explain that there is no problem with the conclusion .

Consider how to quickly maintain and modify .
A node x Received a son son “ A big family ” If and only if $2\ast s_{son}\ge s_x+1$. Obviously there is at most one such son , Define it as $hso{n}_x$（ Special ,$hso{n}_x$ It can be for x own ）,$(x,hso{n}_x)$ Such an edge is defined as a real edge , Other edges are defined as virtual edges .
Consider a node x + w, The change of contribution must be a atavism chain . further , Find a real edge on the atavistic chain , His father's contribution will not change .
Then I feel that the virtual and real sides change, and I won't .

Next , Through the proof similar to tree section , It can be concluded that there are at most $\log a_i$ strip .
Therefore, violent jump can modify the contribution of all virtual edges .
Implementation , After the tree is dissected, two segment trees are opened , A tree to maintain the virtual and real edges , One tree maintenance $s_x$ that will do .
Time complexity $O(n\log n(\log n+\log \sum a_i))$.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")

inline ll read() {
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-') f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=4e5+100;
const int mod=1e9+7;

bool mem1;

inline ll ksm(ll x,ll k){
    
  ll res(1);
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m;

struct seg{
    
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
  ll sum[N<<2],laz[N<<2];
  inline void pushup(int k){
    
    sum[k]=sum[ls]+sum[rs];
  }
  inline void add(int k,int l,int r,ll w){
    
    sum[k]+=(r-l+1)*w;
    laz[k]+=w;
  }
  inline void pushdown(int k,int l,int r){
    
    ll o=laz[k];laz[k]=0;
    if(!o) return;
    add(ls,l,mid,o);
    add(rs,mid+1,r,o);
    return;
  }
  void change(int k,int l,int r,int x,int y,ll w){
    
    if(x<=l&&r<=y){
    
      add(k,l,r,w);return;
    }
    pushdown(k,l,r);
    if(x<=mid) change(ls,l,mid,x,y,w);
    if(y>mid) change(rs,mid+1,r,x,y,w);
    pushup(k);
  }
  int findpre(int k,int l,int r,int p){
    
    if(!k) exit(0);
    //debug("k=%d (%d %d) p=%d\n",k,l,r,p);
    if(!sum[k]) return 0;
    if(l==r) return l;
    if(p<=mid) return findpre(ls,l,mid,p);
    pushdown(k,l,r);
    int o=findpre(rs,mid+1,r,p);
    if(o) return o;
    else return findpre(ls,l,mid,p);
  }
  ll ask(int k,int l,int r,int p){
    
    if(l==r) return sum[k];
    pushdown(k,l,r);
    if(p<=mid) return ask(ls,l,mid,p);
    else return ask(rs,mid+1,r,p);
  }
}t1,t2;
//t1:s
//t2:tag

ll a[N],s[N],mx[N],ans;
int hson[N],siz[N],top[N],dep[N],fa[N],dfn[N],pos[N],tim;
bool tag[N];
vector<int>e[N];
void dfs1(int x,int f){
    
  siz[x]=1;
  dep[x]=dep[f]+1;
  fa[x]=f;
  
  s[x]=mx[x]=a[x];hson[x]=x;
  for(int to:e[x]){
    
    if(to==f) continue;
    dfs1(to,x);
    siz[x]+=siz[to];
    s[x]+=s[to];
    if(s[to]>mx[x]){
    
      hson[x]=to;
      mx[x]=s[to];
    }
  }
  ans+=min(s[x]-1,2*(s[x]-mx[x]));
  ll sh=hson[x]==x?a[x]:s[hson[x]];
  if(2*sh<s[x]+1) hson[x]=0;
  if(hson[x]&&hson[x]!=x) tag[hson[x]]=1;
  return;
}
void dfs2(int x,int tp){
    
  //debug("x=%d tp=%d\n",x,tp);
  top[x]=tp;
  dfn[++tim]=x;pos[x]=tim;
  int son=0;
  for(int to:e[x]){
    
    if(to==fa[x]) continue;
    if(siz[to]>siz[son]) son=to;
  }
  if(son) dfs2(son,tp);
  for(int to:e[x]){
    
    if(to==fa[x]||to==son) continue;
    dfs2(to,to);
  }
  return;
}
void init(){
      
  dfs1(1,0);
  dfs2(1,1);
  for(int i=1;i<=n;i++){
    
    t1.change(1,1,n,pos[i],pos[i],s[i]);
    if(i>1&&!tag[i]) t2.change(1,1,n,pos[i],pos[i],1);
    //printf("i=%d hson=%d s=%lld tag=%d\n",i,hson[i],s[i],tag[i]);
  }
  return;
}
inline ll calc(ll s,ll mx){
    
  return min(s-1,2*(s-mx));
}

inline void upd(int x,int w){
    
  int ori=x;
  //printf("upd: x=%d w=%d\n",x,w);
  if(hson[x]!=x){
    
    int son=hson[x];
    ll sh=son?t1.ask(1,1,n,pos[son]):0,sx=t1.ask(1,1,n,pos[x]);    
    ans-=calc(sx,sh);
    ans+=calc(sx+w,max(sh,a[x]+w));
    //printf(" x=%d son=%d sh=%lld ans=%lld\n",x,son,sh,ans);
    if(son&&2*sh<(sx+w)+1){
       t2.change(1,1,n,pos[son],pos[son],1); hson[x]=0; } if(2*(a[x]+w)>(sx+w)+1){
    
      hson[x]=x;
    }
  }
  while(x){
    
    int p=t2.findpre(1,1,n,pos[x]);
    if(p==0||p<pos[top[x]]) x=fa[top[x]];
    else{
    
      x=dfn[p];
      int son=hson[fa[x]];
      ll sf=t1.ask(1,1,n,pos[fa[x]]),
	sh=son?son==fa[x]?a[fa[x]]:t1.ask(1,1,n,pos[son]):0,sx=t1.ask(1,1,n,pos[x]);      
      ans-=calc(sf,sh);
      ans+=calc(sf+w,max(sx+w,sh));
      //printf(" x=%d son=%d sf=%lld sh=%lld sx=%lld p=%d ans=%lld\n",x,son,sf,sh,sx,p,ans);
      if(son&&2*sh<(sf+w)+1){
    
	t2.change(1,1,n,pos[son],pos[son],1);
	hson[fa[x]]=0;
      }
      if(2*(sx+w)>=(sf+w)+1){
    
	t2.change(1,1,n,pos[x],pos[x],-1);
	hson[fa[x]]=x;
      }
      x=fa[x];
    }
  }
  x=ori;
  a[x]+=w;
  while(x){
    
    t1.change(1,1,n,pos[top[x]],pos[x],w);
    x=fa[top[x]];
  }
  return;
}

bool mem2;
signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();m=read();
  for(int i=1;i<=n;i++) a[i]=read();
  for(int i=1;i<n;i++){
    
    int x=read(),y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  init();
  printf("%lld\n",ans);
  for(int i=1;i<=m;i++){
    
    int x=read(),w=read();
    upd(x,w);
    printf("%lld\n",ans);
  }
  return 0;
}
/* */