https://www.luogu.com.cn/problem/P4751

动态DP

树剖的动态DP做法见此，动态DP原理也再里面，这篇博客就不写了：树剖动态DP

由于树剖时间复杂度为\(O(n \log^2 n)\)，会被这道题卡，所以我们需要全局平衡二叉树

全局平衡二叉树类似\(LCT\)，有虚实边之分，我们把所有的重边作为实边，轻边作为虚边，强行构造一颗\(LCT\)

全局平衡二叉树可以看做一颗静态的\(LCT\)，因为我们已经强行把实边、轻边是哪些边，以及树的结构都钦定了，所以我们无法利用\(Splay\)等操作修改树的结构，但是我们也不需要

也就是说，对于每一条重链，我们都构建一棵二叉搜索树，对于根节点，它的左儿子都是它的父亲，右儿子都是它的子孙（与\(LCT\)极其类似），然后用轻边连接起来

注意，由于全局平衡二叉树一堆二叉搜索树用轻边连接组成，可以沿轻边修改，所以对于一条重链的每个节点，它都挂着一棵轻子树，因此，我们钦定的这条重链的根是带权的，这样才能满足全局平衡（一个节点的权重为其轻子树的大小加上自己\(size_{light}+1\)）

找到一条链的根，可以二分（暴力枚举也没问题），然后继续递归左右子树，最终建成二叉搜索树，这棵二叉搜索树的根的父亲为这棵二叉搜索树所代表的重链的父亲（其实会\(LCT\)的根本不需要解释）

那么修改时就暴力跳父亲，如果是重边，直接\(update\)，如果是轻边，那么就消除原有的贡献，加上新的贡献

时间复杂度：\(O(n \log n)\)

\(Code:\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005
#define INF 1000000007
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define fa(x) F[x]
using namespace std;
int n,m,x,y,tot,rt,lst=0,v[N],F[N],fr[N],d[N << 1],nxt[N << 1];
int sz[N],son[N],q[N],qz[N];
int f[N][2],g[N][2],ch[N][2];
inline int Rmn(int x,int y)
{
    return (x<y)?x:y;
}
inline int Rmx(int x,int y)
{
    return (x>y)?x:y;
}
struct mat
{
    int w[2][2];
    inline mat operator * (mat b)
    {
        mat c;
        c.w[0][0]=Rmx(w[0][0]+b.w[0][0],w[0][1]+b.w[1][0]);
        c.w[0][1]=Rmx(w[0][0]+b.w[0][1],w[0][1]+b.w[1][1]);
        c.w[1][0]=Rmx(w[1][0]+b.w[0][0],w[1][1]+b.w[1][0]);
        c.w[1][1]=Rmx(w[1][0]+b.w[0][1],w[1][1]+b.w[1][1]);
        return c;
    }
}z[N],s[N];
void Rs(mat &q,int a,int b,int c,int d)
{
    q.w[0][0]=a,q.w[0][1]=b;
    q.w[1][0]=c,q.w[1][1]=d;
}
inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')
            w=-1;
        c=getchar();
    }
    while ('0'<=c && c<='9')
        s=s*10+c-'0',c=getchar();
    return s*w;
}
void write(int x)
{
    if (x>9)
        write(x/10);
    putchar(x%10+'0');
}
void add(int x,int y)
{
    tot++;
    d[tot]=y;
    nxt[tot]=fr[x];
    fr[x]=tot;
}
void dfs(int u)
{
    int mx=0;
    sz[u]=1;
    for (int i=fr[u];i;i=nxt[i])
    {
        int v=d[i];
        if (v==fa(u))
            continue;
        fa(v)=u;
        dfs(v);
        sz[u]+=sz[v];
        if (sz[v]>mx)
        {
            mx=sz[v];
            son[u]=v;
        }
    }
}
bool isrt(int x)
{
    return ls(fa(x))!=x && rs(fa(x))!=x;
}
void update(int x)
{
    s[x]=s[ls(x)]*z[x]*s[rs(x)];
}
int build(int l,int r)
{
    if (l>r)
        return 0;
    int sm=qz[r]-qz[l-1];
    sm=(sm+1) >> 1;
    int L=l,R=r,nrt;
    while (L<=R)
    {
        int mid=(L+R) >> 1;
        if (qz[mid]-qz[l-1]>=sm)
        {
            nrt=mid;
            R=mid-1;
        } else
            L=mid+1;
    }
    ls(q[nrt])=build(l,nrt-1);
    rs(q[nrt])=build(nrt+1,r);
    fa(ls(q[nrt]))=q[nrt];
    fa(rs(q[nrt]))=q[nrt];
    update(q[nrt]);
    return q[nrt];
}
void dfs2(int u)
{
    g[u][0]=0;
    g[u][1]=v[u];
    if (!son[u])
    {
        Rs(z[u],0,-INF,v[u],-INF);
        f[u][0]=g[u][0],f[u][1]=g[u][1];
        if (son[fa(u)]!=u)
        {
            int rf=fa(u);
            q[0]=0,qz[0]=0;
            for (int v=u;v;v=son[v])
                q[++q[0]]=v,qz[q[0]]=qz[q[0]-1]+sz[v]-sz[son[v]];
            rt=build(1,q[0]);
            fa(rt)=rf;
        }
        return;
    }
    dfs2(son[u]);
    for (int i=fr[u];i;i=nxt[i])
    {
        int v=d[i];
        if (v==fa(u) || v==son[u])
            continue;
        dfs2(v);
        g[u][0]+=Rmx(f[v][0],f[v][1]);
        g[u][1]+=f[v][0];
    }
    f[u][0]=g[u][0]+Rmx(f[son[u]][0],f[son[u]][1]);
    f[u][1]=g[u][1]+f[son[u]][0];
    Rs(z[u],g[u][0],g[u][0],g[u][1],-INF);
    if (son[fa(u)]!=u)
    {
        int rf=fa(u);
        q[0]=0,qz[0]=0;
        for (int v=u;v;v=son[v])
            q[++q[0]]=v,qz[q[0]]=qz[q[0]-1]+sz[v]-sz[son[v]];
        rt=build(1,q[0]);
        fa(rt)=rf;
    }
}
void modify(int x,int y)
{
    g[x][1]=g[x][1]-v[x]+y;
    v[x]=y;
    Rs(z[x],g[x][0],g[x][0],g[x][1],-INF);
    for (int u=x;u;u=fa(u))
        if (isrt(u) && fa(u))
        {
            int v=fa(u);
            g[v][0]-=Rmx(s[u].w[0][0],s[u].w[1][0]);
            g[v][1]-=s[u].w[0][0];
            update(u);
            g[v][0]+=Rmx(s[u].w[0][0],s[u].w[1][0]);
            g[v][1]+=s[u].w[0][0];
            Rs(z[v],g[v][0],g[v][0],g[v][1],-INF);
        } else
            update(u);
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        v[i]=read();
    for (int i=1;i<n;i++)
    {
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1);
    Rs(z[0],0,-INF,-INF,0);
    Rs(s[0],0,-INF,-INF,0);
    dfs2(1);
    while (m --> 0)
    {
        x=read(),y=read(),x^=lst;
        modify(x,y);
        lst=Rmx(s[rt].w[0][0],s[rt].w[1][0]);
        write(lst),putchar('\n');
    }
    return 0;
}