#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N=400050;
char rB[1<<21],*S,*T,wB[1<<21];
int wp=-1;
inline char gc(){return S==T&&(T=(S=rB)+fread(rB,1,1<<21,stdin),S==T)?EOF:*S++;}
inline void flush(){fwrite(wB,1,wp+1,stdout);wp=-1;}
inline void pc(char c){if(wp+1==(1<<21))flush();wB[++wp]=c;}
inline int rd(){
    char c=gc();
    while(c<48||c>57)c=gc();
    int x=c&15;
    for(c=gc();c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c&15);
    return x;
}
short buf[25];
inline void wt(ll x){
    short l=-1;
    while(x>9){
        buf[++l]=x%10;
        x/=10;
    }
    pc(x|48);
    while(l>=0)pc(buf[l--]|48);
    pc('\n');
}
int G[N],to[N<<1],nxt[N<<1],sz=0,f[N],ch[N][2],r[N];
ll a[N],sum[N],ima[N],ans=0;
queue<int> Q;
inline void pushup(int o){sum[o]=a[o]+sum[ch[o][0]]+sum[ch[o][1]]+ima[o];}
inline bool dir(int o){return ch[f[o]][1]==o;}
inline bool isrt(int o){return ch[f[o]][0]!=o&&ch[f[o]][1]!=o;}
inline ll calc(int u,ll s,ll h){return ch[u][1]?(s-h<<1):((a[u]<<1)>s?(s-a[u]<<1):s-1);}  //计算冲突值
inline void rot(int o){
    int fa=f[o];
    bool d=dir(o);
    f[o]=f[fa];
    if(!isrt(fa))ch[f[fa]][dir(fa)]=o;
    if(ch[fa][d]=ch[o][d^1])f[ch[fa][d]]=fa;
    f[ch[o][d^1]=fa]=o;
    pushup(fa);pushup(o);
}
inline void splay(int o){
    for(;!isrt(o);rot(o))if(!isrt(f[o]))rot((dir(f[o])^dir(o))?o:f[o]);
}
//LCT的Splay部分
inline void add(int u,int v){
    to[++sz]=v;nxt[sz]=G[u];G[u]=sz;
    to[++sz]=u;nxt[sz]=G[v];G[v]=sz;
}
inline void work(int u){  //处理u
    int i,v,p=0;
    ll maxn=a[u];
    sum[u]=a[u];
    for(i=G[u];i;i=nxt[i])if((v=to[i])!=f[u]){
        sum[u]+=sum[v];
        if(sum[v]>maxn)maxn=sum[p=v];
    }
    ans+=(maxn<<1)>sum[u]?(sum[u]-maxn<<1):sum[u]-1;
    if(p&&(maxn<<1)>sum[u])ch[u][1]=p;  //计算答案和加边
    ima[u]=sum[u]-sum[ch[u][1]]-a[u];  //把u的虚儿子的值储存下来，以完成子树Su大小的计算
}
inline void update(int x,int w){  //更新
    int y=x;
    splay(x);
    ll s=sum[x]-sum[ch[x][0]],h=sum[ch[x][1]];
    ans-=calc(x,s,h);
    a[x]+=w;sum[x]+=w;s+=w;
    if((h<<1)<=s){ima[x]+=h;ch[x][1]=0;}
    ans+=calc(x,s,h);
    pushup(x);
    for(x=f[x];x;x=f[y=x]){
        splay(x);
        s=sum[x]-sum[ch[x][0]];h=sum[ch[x][1]];
        ans-=calc(x,s,h);
        sum[x]+=w;ima[x]+=w;s+=w;
        if((h<<1)<=s){
            ima[x]+=h;ch[x][1]=h=0;
            if((sum[y]<<1)>s){  //切换（必须满足新的值可以成为新的实儿子才切换）
                ima[x]-=(h=sum[y]);
                ch[x][1]=y;
            }
        }
        ans+=calc(x,s,h);
        pushup(x);
    }
}
int main(){
    int n=rd(),m=rd(),i,u,v,tot=1;
    for(i=1;i<=n;++i)a[i]=rd();
    for(i=1;i<n;++i){
        u=rd();v=rd();
        add(u,v);
    }
    Q.push(r[1]=1);
    while(!Q.empty()){
        u=Q.front();Q.pop();
        for(i=G[u];i;i=nxt[i])if((v=to[i])!=f[u]){
            f[v]=u;
            r[++tot]=v;
            Q.push(v);
        }
    }
    //求拓扑序
    for(i=n;i;--i)work(r[i]);  //倒序处理，保证u的儿子先于u处理
    wt(ans);
    while(m--){
        u=rd();v=rd();
        update(u,v);
        wt(ans);
    }
    flush();
    return 0;
}

给定一棵树，已知每个点的access次数，求虚/实边切换次数的最大值。
首先不考虑修改，设一个点u修改次数为au，下属子树的总修改次数为Su，hu=max{au,max{Sv}(v为u的子节点)}，则可知2h>Su时，u结点的最大冲突次数为2(Su-h)；否则为Su-1。（可以自己试几次，保证理解）
对于2h>Su的结点，我们注意到修改它Sv==h的孩子时答案是不变的，只有修改其它孩子时答案才发生变化，所以我们从u向它连一条实边（不难看出这样的实边最多只有一条），其它孩子连虚边，则可以用LCT维护，只有沿虚边向上跳时才需要考虑更新答案和虚实边切换（可能不切换，这点要注意）。
可以发现这种连法具有类似树剖的良好性质，复杂度O(mlongn)
不过出于一些奇怪的原因Vijos上初始化的dfs会爆栈，考虑用bfs求出拓扑序，然后逆着拓扑序处理即可。
code：

#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N=400050;
char rB[1<<21],*S,*T,wB[1<<21];
int wp=-1;
inline char gc(){return S==T&&(T=(S=rB)+fread(rB,1,1<<21,stdin),S==T)?EOF:*S++;}
inline void flush(){fwrite(wB,1,wp+1,stdout);wp=-1;}
inline void pc(char c){if(wp+1==(1<<21))flush();wB[++wp]=c;}
inline int rd(){
    char c=gc();
    while(c<48||c>57)c=gc();
    int x=c&15;
    for(c=gc();c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c&15);
    return x;
}
short buf[25];
inline void wt(ll x){
    short l=-1;
    while(x>9){
        buf[++l]=x%10;
        x/=10;
    }
    pc(x|48);
    while(l>=0)pc(buf[l--]|48);
    pc('\n');
}
int G[N],to[N<<1],nxt[N<<1],sz=0,f[N],ch[N][2],r[N];
ll a[N],sum[N],ima[N],ans=0;
queue<int> Q;
inline void pushup(int o){sum[o]=a[o]+sum[ch[o][0]]+sum[ch[o][1]]+ima[o];}
inline bool dir(int o){return ch[f[o]][1]==o;}
inline bool isrt(int o){return ch[f[o]][0]!=o&&ch[f[o]][1]!=o;}
inline ll calc(int u,ll s,ll h){return ch[u][1]?(s-h<<1):((a[u]<<1)>s?(s-a[u]<<1):s-1);}  //计算冲突值
inline void rot(int o){
    int fa=f[o];
    bool d=dir(o);
    f[o]=f[fa];
    if(!isrt(fa))ch[f[fa]][dir(fa)]=o;
    if(ch[fa][d]=ch[o][d^1])f[ch[fa][d]]=fa;
    f[ch[o][d^1]=fa]=o;
    pushup(fa);pushup(o);
}
inline void splay(int o){
    for(;!isrt(o);rot(o))if(!isrt(f[o]))rot((dir(f[o])^dir(o))?o:f[o]);
}
//LCT的Splay部分
inline void add(int u,int v){
    to[++sz]=v;nxt[sz]=G[u];G[u]=sz;
    to[++sz]=u;nxt[sz]=G[v];G[v]=sz;
}
inline void work(int u){  //处理u
    int i,v,p=0;
    ll maxn=a[u];
    sum[u]=a[u];
    for(i=G[u];i;i=nxt[i])if((v=to[i])!=f[u]){
        sum[u]+=sum[v];
        if(sum[v]>maxn)maxn=sum[p=v];
    }
    ans+=(maxn<<1)>sum[u]?(sum[u]-maxn<<1):sum[u]-1;
    if(p&&(maxn<<1)>sum[u])ch[u][1]=p;  //计算答案和加边
    ima[u]=sum[u]-sum[ch[u][1]]-a[u];  //把u的虚儿子的值储存下来，以完成子树Su大小的计算
}
inline void update(int x,int w){  //更新
    int y=x;
    splay(x);
    ll s=sum[x]-sum[ch[x][0]],h=sum[ch[x][1]];
    ans-=calc(x,s,h);
    a[x]+=w;sum[x]+=w;s+=w;
    if((h<<1)<=s){ima[x]+=h;ch[x][1]=0;}
    ans+=calc(x,s,h);
    pushup(x);
    for(x=f[x];x;x=f[y=x]){
        splay(x);
        s=sum[x]-sum[ch[x][0]];h=sum[ch[x][1]];
        ans-=calc(x,s,h);
        sum[x]+=w;ima[x]+=w;s+=w;
        if((h<<1)<=s){
            ima[x]+=h;ch[x][1]=h=0;
            if((sum[y]<<1)>s){  //切换（必须满足新的值可以成为新的实儿子才切换）
                ima[x]-=(h=sum[y]);
                ch[x][1]=y;
            }
        }
        ans+=calc(x,s,h);
        pushup(x);
    }
}
int main(){
    int n=rd(),m=rd(),i,u,v,tot=1;
    for(i=1;i<=n;++i)a[i]=rd();
    for(i=1;i<n;++i){
        u=rd();v=rd();
        add(u,v);
    }
    Q.push(r[1]=1);
    while(!Q.empty()){
        u=Q.front();Q.pop();
        for(i=G[u];i;i=nxt[i])if((v=to[i])!=f[u]){
            f[v]=u;
            r[++tot]=v;
            Q.push(v);
        }
    }
    //求拓扑序
    for(i=n;i;--i)work(r[i]);  //倒序处理，保证u的儿子先于u处理
    wt(ans);
    while(m--){
        u=rd();v=rd();
        update(u,v);
        wt(ans);
    }
    flush();
    return 0;
}

首先有一个简单的结论是:任意时间内一个城市控制的区域一定是一条它到自己的一个祖先的路径

原因也很显然:我们每次更改一个点所属的城市的时候也会同时修改它的所有祖先的控制权，不会出现将一个城市控制的区域被截成两半的情况

那么根据这个结论我们可以将同一个城市控制的区域看成一条重链,各个重链之间通过不是重边的轻边相连

此时一次“崛起”操作的权值就是点i到1路径上的重链条数了,当然前提是i没有控制任何城市,如果i控制了一个城市的话权值就需要减1了

似乎这样计算权值需要分情况讨论还是有点麻烦……让我们尝试继续简化题目给出的条件

我们发现点i到1路径上的重链条数=点i到1路径上的轻边个数+1

但是此时我们依然需要分情况讨论啊……怎么办呢？

有一个性质是当点i至少控制了一个城市时,点i的崛起不会改变点i下面的边的轻重属性

但是如果点i没有控制任何城市的时候，点i的崛起会改变点i下面边的轻重属性

根据这个性质我们可以绕开分情况讨论了,我们此时可以很快的推出一次“崛起”操作的权值是本次操作中的轻重边切换次数

因为点i到1路径上的重边一定不会被切换而轻边一定会被切换并且当点i没有控制任何城市的时候会额外发生一次轻重边切换,所以一次"崛起"操作中的轻重边切换次数就等于点i到1路径上轻边个数+[点i是否没有控制任何城市],这与我们刚才推出来一次"崛起"操作的权值等于点i到1路径上的重链条数-[点i是否控制了至少一个城市]是等价的

既然我们最大化的东西轻重边切换次数之和(一开始没有重边所有边都是轻边)那么问题就会变得稍微好考虑一点,我们考虑每个点对答案的贡献，换句话就是最大化每个点下面的边的轻重边切换次数之和(显然一个点下面最多有一条重边也可能一条重边都没有)

那么我们发现一个点ii的轻重边发生切换只会受到来自自己子树的操作的影响

并且发生切换的条件是时间上相邻的两个操作来自于不同的子树或者其中是一个是来自于点i的操作另一个不是来自点i的操作，换句话说和这个操作到底来自于那个点是无关的而仅仅和这个操作来自的子树有关

那么假设我们可以对一个点i安排出一个最优的操作序列，我们就可以在树上dfs，先对当前dfs到的点u的所有子树做出最优的安排，接下来再把这些操作序列按照一种对点u最优的方式"混合"在一起如此这般递归下去我们就可以构造出一个全局最优的的方案了

所以我们现在唯一需要关心的事情就是如何最大化某一个点i的轻重边切换次数，然后我们把每一个点算出来的次数加起来就是我们要的答案

那么这就是一个比较经典的结论了,给你若干种不同颜色的小球要求你把这些小球摆成一列,最大化相邻的不同色球的数目

那么这里有一个结论是我们设球的总数是SS最大值是MxMx的话答案是

min(S-1,2(S-Mx))
min(S−1,2(S−Mx))
证明的话就是当最大的颜色不过半的时候我们总是可以采取这样的一种贪心策略就是每次都选和上一个球颜色不同的球当中最多的一个球来作为我们放的下一个球，由于最大颜色种类不会过半因此我们总是可以成功构造一种方案出来 此时我们的答案就是S-1S−1
但是如果最大种类过半的话我们会发现刚才的做法是失效的,此时我们的策略就是把这种最大的颜色看成一种颜色然后将其余的所有颜色都插入这种最大的颜色当中,采用这种策略构造出来的结果就是2(S-Mx)2(S−Mx)了

因此题目让我们计算的式子就是了

\sum_{i=1}^{n}min(S_{i}-1,2(S_{i}-Mx_{i}))
i=1
∑
n
​ min(S
i
​ −1,2(S
i
​ −Mx
i
​ ))
修改相当于将一条以1为端点的链上的S_{i}S
i
​ 值加上ww
那么我们发现由于我们维护的式子是一个取min的操作,在我们我们取min的分界线就是S+1 \leq 2Mx_{i}S+1≤2Mx
i
​ 如果这个式子为真那么我们的答案将不再是S-1S−1而是2(S-Mx)2(S−Mx)了

按理说如果是一般的修改我们是没办法维护这个式子的

但是我们的修改有个相当强的性质就是我们每次都给整条链加上一个数字ww
注意这里是加而不是减

那么对于一对父子(u,v)(u,v)如果v是u的带权siz最大的子树的话,v和u的siz同时被加上一个值v依然是u的最大的子树，并且如果v已经已经是u的过半的子树的话，v和u的siz同时加上一个值v依然是u的过半子树

那么我们可以仿照树链剖分中的轻重边定义,定义带权意义下的轻重边

我们定义一个点的所有孩子当中,带权siz最大的点为这个点的重儿子

我们定义如果一个点重儿子的siz已经过半，那么这个点和它的重儿子之间的边为一条重边,其余的边全部是轻边

注意这个定义下一个点和它重儿子之间的边可以是一条轻边

那么我们会有一个比较显然的结论是每经过一条轻边所在子树的带权siz必然翻倍,所以任意一个点到1的路径上至多有log(\sum a_{i})log(∑a
i
​ )条轻边

让我们接着观察当一对父子(u,v)(u,v)的siz同时被加上w的时候uu的答案会作何变换

如果(u,v)(u,v)这条边是一条重边的话你会发现答案并不会被改动,同时uu的重儿子和轻重边关系也不会被改变

所以答案发生变化的边必然是一条轻边,重儿子和轻重边关系发生改变的边也必然是一条轻边

那么我们只需要找到1~u1 u路径上的所有轻边然后暴力修改一下即可完成答案的维护工作了

问题是我们如何高效找到一条轻边呢？

答案是使用类似于lct一样的数据结构(但是只是一个类似的数据结构并不是lct)

我们保证在同一条重链中的点都在同一个splay当中,并且按照深度排好序,那么我们寻找下一条轻边的操作就是在splay当中查找最小值,将链上的点加上一个值可以通过打标记来实现,将轻边变成重边就是将两个splay接在一起,将重边变成轻边就是一个splay分裂成两个

这样的话我们只需要在若干个splay当中不停的查找最小值就可以完成寻找轻边的任务了

另外一点就是按照我们刚才的定义可能会出现一个点和它的重儿子之间连了一条轻边但是计算答案却按照2(S-Mx)2(S−Mx)计算的情况,这种情况的出现是因为它自己的点权比较大过半了而不是孩子的点权过大了

那么我们维护这种情况比较麻烦所以我们直接特判掉这种情况

具体来讲我们在检查一条轻边(u,v)(u,v)是否会成为重边的时候我们先判一下是否出现自己的点权过半这种情况出现了就直接修改答案而不是继续我们的分情况讨论

还有一些需要画图才能说清楚的细节写注释里了

剩下的事情就是写一个比较简易的splay了

上代码~
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
register LL x=0,f=1;register char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f*x;
}

const int MAXN=4e5+5;
const int MAXM=8e5+5;

struct Edge{
int v,next;
}e[MAXM];
int first[MAXN],Ecnt=1;
inline void Add_edge(int u,int v){
e[++Ecnt]=(Edge){v,first[u]};
first[u]=Ecnt;
}

int n,m;
LL ans;

namespace LCT{
LL sum[MAXN],aux[MAXN],val[MAXN];
int ch[MAXN][2],par[MAXN];
#define ls ch[rt][0]
#define rs ch[rt][1]
inline bool chk(int x){return ch[par[x]][1]==x;}
inline bool nrt(int x){return ch[par[x]][0]==x||ch[par[x]][1]==x;}
inline void pushup(int rt){sum[rt]=sum[ls]+sum[rs]+val[rt]+aux[rt];}//全部加起来
inline void rotate(int x){
int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
ch[y][k]=w,par[w]=y;
if(nrt(y)) ch[z][chk(y)]=x; par[x]=z;
ch[x][k^1]=y,par[y]=x;
pushup(y);pushup(x);
}
inline void splay(int x){
while(nrt(x)){
int y=par[x];
if(nrt(y)){
if(chk(x)==chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
#undef ls
#undef rs
}using namespace LCT;

inline void dfs(int u,int pre){
LL maxp=val[u];int p=0;
sum[u]=val[u],par[u]=pre;
for(int i=first[u];i;i=e[i].next){
int v=e[i].v;
if(v==pre) continue;
dfs(v,u);
sum[u]+=sum[v];
if(sum[v]>maxp) maxp=sum[p=v];
}
ans+=min(sum[u]-1,2*(sum[u]-maxp));
if(maxp*2>=sum[u]+1) ch[u][1]=p;
aux[u]=sum[u]-val[u]-sum[ch[u][1]];
}

#define ls ch[u][0]
#define rs ch[u][1]
inline LL calc(int u,LL total,LL weight){
if(rs) return (total-weight)*2;
else if(val[u]*2>=total+1) return(total-val[u])*2;
else return total-1;
}

inline void modify(int u,int w){
splay(u);
LL total=sum[u]-sum[ls],weight=sum[rs];
ans-=calc(u,total,weight);
sum[u]+=w,val[u]+=w,total+=w;
if(weight*2<=total) aux[u]+=weight,rs=0;
ans+=calc(u,total,weight);
pushup(u);

int v;
for(u=par[v=u];u;u=par[v=u]){
splay(u);
total=sum[u]-sum[ls],weight=sum[rs];
ans-=calc(u,total,weight);
sum[u]+=w,aux[u]+=w,total+=w;//虚边size+=w;
if(weight*2<=total) aux[u]+=weight,rs=0,weight=0;
if(sum[v]*2>=total+1) aux[u]-=sum[v],rs=v,weight=sum[v];
ans+=calc(u,total,weight);
pushup(u);
}
}
#undef ls
#undef rs

int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=n-1;i++){
int x=read(),y=read();
Add_edge(x,y);
Add_edge(y,x);
}
dfs(1,0);
printf("%lld\n",ans);
for(int i=1;i<=m;i++){
int x=read(),y=read();
modify(x,y);
printf("%lld\n",ans);
}
}
```