题解

题目类型：树上动态维护 / 局部贡献拆分 / Splay 旋转辅助
核心目标：一棵树，每个点有点权 a[u]。先输出初始全局答案 ans，之后进行多次单点加权操作 a[x] += w，每次都要在线更新并输出新的 ans。

程序的关键在于：把全局答案拆成每个结点的局部贡献 get(u) 的和，即
[ \textbf{ans} ;=; \sum_{u=1}^{n} \textbf{get}(u)。 ]
只要能在每次修改时，沿着 x → 根 的祖先链把受影响的若干个 u 的贡献从 ans 里删旧加新，即可实现在线维护。

一、数据与含义

• g[u]：树邻接表。
• a[u]：点权，会被修改。
• sz[u]：u 的“有效规模”，后述定义（与 splay 左/右子、轻儿子汇总有关）。
• b[u]：u 所有轻儿子子树规模之和（非当前“重儿子”的那部分）。
• ch[u][0/1]：用于 splay 的左右孩子；ch[u][1] 同时也承担“重儿子”指针的语义（若存在）。
• fa[u]：树上的父亲编号（注意不是 splay 的父亲）。
• ans：全局答案，始终等于所有点贡献 get(u) 之和。

有效规模与上推

void pushup(int u){
    sz[u] = sz[ch[u][0]] + sz[ch[u][1]] + a[u] + b[u];
}

含义：u 的有效规模 = splay 左子规模 + splay 右子规模 + 自身点权 + 轻儿子规模汇总。

局部贡献函数 get(u)

int get(int u){
    int tmp = sz[u] - sz[ch[u][0]];      // 去掉左子后的“当前块”
    if(ch[u][1])                          // 若存在重儿子
        return (tmp - sz[ch[u][1]]) * 2;  // 与“非重儿子部分”的配对量 ×2
    else
        return min(tmp-1, (tmp - a[u]) * 2);
}

直观理解：把 u 的“当前有效块”划分成“重儿子部分”和“其他部分”。

• 若有重儿子，重儿子“吃掉”超过半数，能与之匹配的仅剩“其他部分”，因而贡献约为 2 * 其他部分；
• 若没有重儿子，两种“拼法”的上界分别是 tmp-1（留一作中心）与 (tmp-a[u])*2（仅从“非自身”之间配），取较小值更合理。

这不是某个标准题意的固定公式，而是本代码构造的“可维护的局部最优拼量”。ans 始终维护的是这套规则下的全局和。

二、初始化 dfs

void dfs(int u,int fa){
    ::fa[u]=fa; sz[u]=a[u];
    // 1) 先算子树总 sz
    for (auto v : g[u]) if(v!=fa) dfs(v,u), sz[u]+=sz[v];

    // 2) 选重儿子（若存在），其余进 b[u]
    for (auto v : g[u]) if(v!=fa){
        if (2*sz[v] >= sz[u] + 1) ch[u][1] = v;    // 成为重儿子
        else b[u] += sz[v];                        // 轻儿子汇总
    }

    pushup(u);
    ans += get(u);
}

• 第一次循环统计 sz[u]；
• 第二次循环确定重儿子：满足 2*sz[v] >= sz[u] + 1 的唯一儿子（若有）；其余儿子的规模累加进 b[u]；
• 上推并把 get(u) 纳入 ans。

三、为何需要 splay？

get(u) 的计算用到 sz[ch[u][0]]（splay 左子规模）。在路径更新中，我们希望：

• 每次只更新从修改点到根的一条链；
• 在访问到某个 u 时，让它当前结构的左子恰好是我们想要剔除的那部分，这样 tmp = sz[u]-sz[left] 的值就是“当前块”的规模，于是 get(u) 可被正确重算。

因此采用 splay 把链上结点旋至局部根，并动态调整左右儿的归属。这个 splay 并不需要 Link-Cut Tree 的全功能，只做“旋到根 + 左剔除”的辅助。

四、单点加权 tong(x, w)：沿祖先链删旧加新

void tong(int x,int w){
    int pre=0;
    while(x){
        splay(x);
        ans -= get(x);                   // 先删旧贡献

        if(pre==0) a[x]+=w;              // 起点：修改 a[x]
        else       b[x]+=w;              // 往上走：轻儿子和 b[祖先]+=w
        sz[x] += w;                      // 有效规模也要加

        // 原重儿是否失去“重”的资格
        if(ch[x][1]){
            if( 2*sz[ch[x][1]] < sz[x] - sz[ch[x][0]] + 1 ){
                b[x] += sz[ch[x][1]];
                ch[x][1] = 0;
                pushup(x);
            }
        }

        // 当前走上来的这一支 pre 是否应被提升为新“重儿子”
        if(pre){
            if( 2*sz[pre] >= sz[x] - sz[ch[x][0]] + 1 ){
                ch[x][1] = pre;
                b[x] -= sz[pre];
                pushup(x);
            }
        }

        ans += get(x);                   // 加新贡献
        pre = x; x = fa[x];              // 上移到父亲
    }
}

复杂度：每次操作沿一条链做若干次 splay，均摊 O(log n)。

五、整体流程

1. 读入 n,m、点权 a[i] 与树边。
2. dfs(1,0) 初始化 sz / b / ch[][1] / ans。
3. 输出初始 ans。
4. 循环 m 次：
   • 读入 (x, w)；
   • 调用 tong(x, w) 在线更新；
   • 输出新的 ans。

六、复杂度

• 建树 + DFS 初始化：O(n)
• 每次修改：祖先链长度 × splay 旋转，均摊 O(log n)
• 总体：O((n + m) log n)，数组规模开到 1e6+5 以应对大数据。

七、完整代码（与题给一致）

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int ans,a[1001001],b[1001001];
int n,m;
int tag[1001001];
vector<int>g[1001001];
int sz[1001001],fa[1001001],mx[1001001];
int ch[1001001][2];
int get(int x){
    int tmp=sz[x]-sz[ch[x][0]];
    if(ch[x][1])return (tmp-sz[ch[x][1]])*2;
    else return min(tmp-1,(tmp-a[x])*2);
}
void pushup(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+a[x]+b[x];
}
void pushdown(int x){}
void dfs(int x,int pa){
    fa[x]=pa;sz[x]=a[x];mx[x]=n+1;
    for (auto y:g[x])
    if(y!=pa)dfs(y,x),sz[x]+=sz[y];
    for (auto y:g[x])
    if(y!=pa){
        if(sz[y]*2>=sz[x]+1)ch[x][1]=y;
        else b[x]+=sz[y];
    }
    pushup(x);
    ans+=get(x);
}
bool isrt(int x){
    return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
int dir(int x){
    return ch[fa[x]][1]==x;
}
void rotate(int x){
    if(isrt(x))return ;
    int y=fa[x],z=fa[y],l=dir(x),r=l^1;
    if(!isrt(y))ch[z][dir(y)]=x;fa[x]=z;
    ch[y][l]=ch[x][r],fa[ch[x][r]]=y;
    ch[x][r]=y;fa[y]=x;
    pushup(y);pushup(x);
}
void update(int x){
    if(!isrt(x))update(fa[x]);
    pushdown(x);
}
void splay(int x){
    update(x);
    for (int y=fa[x];!isrt(x);rotate(x),y=fa[x])
    if(!isrt(y))rotate(dir(x)==dir(y)?y:x);
}
void tong(int x,int w){
    int pre=0;
    while(x){
        splay(x);
        ans-=get(x);
        if(pre==0)a[x]+=w;
        else b[x]+=w;sz[x]+=w;
        if(ch[x][1]){
            if(sz[ch[x][1]]*2<sz[x]-sz[ch[x][0]]+1)
            b[x]+=sz[ch[x][1]],ch[x][1]=0,pushup(x);
        }
        if(pre){
            if(sz[pre]*2>=sz[x]-sz[ch[x][0]]+1)ch[x][1]=pre,b[x]-=sz[pre],pushup(x);
        }
        ans+=get(x);
        pre=x;x=fa[x];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    for (int i=1,x,y;i<n;i++)
    cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
    dfs(1,0);
    cout<<ans<<"\n";
    while(m--){
        int x,y;
        cin>>x>>y;
        tong(x,y);
        cout<<ans<<"\n";
    }
}