luoguP4719【模板】动态dp

#include
#include
#include
#include
#include
#include
using namespace std;

struct node
{
    int x,y,next;
}a[210000];int len,last[110000];
void ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct Matrix
{
    int mp[3][3];
    Matrix(){memset(mp,-31,sizeof(mp));}
    Matrix(int A,int B,int C,int D)
    {
        memset(mp,-31,sizeof(mp));
        mp[1][1]=A,mp[1][2]=B,mp[2][1]=C,mp[2][2]=D;
    }
    friend Matrix operator *(Matrix a,Matrix b)
    {
        Matrix c;
        memset(c.mp,-31,sizeof(c.mp));
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    c.mp[i][j]=max(c.mp[i][j],a.mp[i][k]+b.mp[k][j]);
        return c;
    }
}f[110000],g[110000];//当前点答案，转移矩阵 
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct trnode//用于求l~r的转移矩阵乘积（带修） 
{
    int l,r,lc,rc;
    Matrix m;
}tr[210000];int trlen;
void tr_bt(int l,int r)
{
    int now=++trlen;
    tr[now].l=l;tr[now].r=r;
    tr[now].lc=tr[now].rc=-1;
    tr[now].m=Matrix(0,-(1<<29),-(1<<29),0);
    if(l<r)
    {
        int mid=(l+r)/2;
        tr[now].lc=trlen+1;tr_bt(l,mid);
        tr[now].rc=trlen+1;tr_bt(mid+1,r);
    }
}
void tr_change(int now,int p,int x)
{
    if(tr[now].l==tr[now].r){tr[now].m=g[x];return ;}
    int mid=(tr[now].l+tr[now].r)/2;
    int lc=tr[now].lc,rc=tr[now].rc;
    if(p<=mid)tr_change(lc,p,x);
    else       tr_change(rc,p,x);
    tr[now].m=tr[lc].m*tr[rc].m;
}
Matrix tr_getmatrix(int now,int l,int r)
{
    if(tr[now].l==l&&tr[now].r==r)return tr[now].m;
    int mid=(tr[now].l+tr[now].r)/2;
    int lc=tr[now].lc,rc=tr[now].rc;
         if(r<=mid)  return tr_getmatrix(lc,l,r);
    else if(mid+1<=l)return tr_getmatrix(rc,l,r);
    else return tr_getmatrix(lc,l,mid)*tr_getmatrix(rc,mid+1,r);
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//-------------------------------------------------struct----------------------------------------------------------------

int fa[110000],son[110000],tot[110000],dep[110000];
void pre_tree_node(int x)
{
    tot[x]=1,son[x]=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa[x])
        {
            fa[y]=x;
            dep[y]=dep[x]+1;
            pre_tree_node(y);
            if(son[x]==0||tot[son[x]]y;
            tot[x]+=tot[y];
        }
    }
}
int z,ys[110000];
int cnt,bel[110000],L[110000],R[110000];
void pre_tree_edge(int x,int wi)
{
    ys[x]=++z;bel[x]=wi;
    if(son[x]!=0)pre_tree_edge(son[x],wi);
    else R[wi]=x;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa[x]&&y!=son[x])
        {
            L[++cnt]=y;
            pre_tree_edge(y,cnt);
        }
    }
}
void reverse()
{
    for(int i=1;i<=cnt;i++)
    {
        int ll=ys[L[i]],rr=ys[R[i]],now=R[i];
        for(int j=ll;j<=rr;j++)ys[now]=j,now=fa[now];
    }
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int w[110000]; 
void dfs(int x)
{
    f[x].mp[1][1]=0,f[x].mp[1][2]=w[x];
    if(son[x]==0)return ;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y!=fa[x])
        {
            dfs(y);
            f[x].mp[1][1]+=max(f[y].mp[1][1],f[y].mp[1][2]);
            f[x].mp[1][2]+=f[y].mp[1][1];
        }
    }
    g[x].mp[1][1]=f[x].mp[1][1]-max(f[son[x]].mp[1][1],f[son[x]].mp[1][2]);
    g[x].mp[2][1]=f[x].mp[1][1]-max(f[son[x]].mp[1][1],f[son[x]].mp[1][2]);
    g[x].mp[1][2]=f[x].mp[1][2]-f[son[x]].mp[1][1];
    g[x].mp[2][2]=-(1<<29);
    tr_change(1,ys[x],x);
}

//-----------------------------------------------------init--------------------------------------------------------------------

Matrix tt;
void update(int y)
{
    while(L[bel[y]]==y&&fa[y]!=0)
    {
        int x=fa[y];
        
        int d1=g[x].mp[1][1],d2=g[x].mp[1][2];
        d1-=max(tt.mp[1][1],tt.mp[1][2]);
        d2-=tt.mp[1][1];
        d1+=max(f[y].mp[1][1],f[y].mp[1][2]);
        d2+=f[y].mp[1][1];
    
        g[x].mp[1][1]=g[x].mp[2][1]=d1;
        g[x].mp[1][2]=d2;
        tr_change(1,ys[x],x);
        
        int u=R[bel[x]];tt=f[x];
        f[x]=f[u]*tr_getmatrix(1,ys[fa[u]],ys[x]);
        
        y=x;
    }
}
void change(int x,int k)
{
    if(L[bel[x]]==x)tt=f[x];
    
    if(son[x]==0)f[x].mp[1][2]+=-w[x]+k;
    else 
    {    
        g[x].mp[1][2]+=-w[x]+k;
        tr_change(1,ys[x],x);
        
        int u=R[bel[x]];
        f[x]=f[u]*tr_getmatrix(1,ys[fa[u]],ys[x]);
    }
    
    if(L[bel[x]]==x)update(x);
    w[x]=k;
}
void solve(int x)
{
    int tx=L[bel[x]];
    while(x!=0)
    {
        if(tx!=x)
        {
            tt=f[tx];
            f[tx]=f[x]*tr_getmatrix(1,ys[fa[x]],ys[tx]);
            update(tx);
        }
        x=fa[tx],tx=L[bel[x]];
    }
}

//----------------------------------------------------solve--------------------------------------------------------------------

int main()
{
    int n,Q,x,y;
    scanf("%d%d",&n,&Q);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i)
    {
        scanf("%d%d",&x,&y);
        ins(x,y),ins(y,x);
    }
    fa[1]=0,dep[1]=0;pre_tree_node(1);
    z=0,cnt=0,L[1]=1;pre_tree_edge(1,++cnt),reverse();
    trlen=0;tr_bt(1,n);dfs(1);
    
    while(Q--)
    {
        scanf("%d%d",&x,&y);
        change(x,y);solve(x);
        printf("%d\n",max(f[1].mp[1][1],f[1].mp[1][2]));
    }
    
    return 0;
}