动态dp

题目大意：一棵树，点有点权，每次修改点权，询问最大独立集。

不带修改的 dp 不难。动态 dp 的套路就是把转移写成矩阵的形式，然后用线段树维护。我们时刻维护一个数组 g[u]$g[u]$，表示 u$u$ 不从重儿子转移过来的 dp 数组。这样修改一个权值只会影响到 log$\log$ 个 g[u]$g[u]$（他自己和到根的每条重链的下端点）。假设考虑答案的 dp 数组是 f$f$，我们把转移（f[u]−>f[fa[u]]$f[u]->f[fa[u]]$）写成矩阵形式，也就是重儿子的 f$f$ 乘上一个矩阵（矩阵的元素是 g$g$）得到自己的 f$f$，就可以线段树维护由 g$g$ 数组构成的矩阵了。注意这里的矩阵之间不是相乘的关系，而是我们重新定义了一种“取 max”运算，它显然也满足结合律。

基本思想就是：每个点的转移矩阵与它的重儿子无关，这样就保证了只会在线段树里修改 log$\log$ 个矩阵。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
struct edge{
    int to,next;
}ed[200010];
struct Matrix{
    int a[3][3];
}t[400010],I;
int n,m,deep[100010],fa[100010],w[100010],size[100010],son[100010],head[100010],sz,f[100010][2],g[100010][2],ind[100010],pre[100010],top[100010],bot[100010],tim;
Matrix operator * (Matrix a,Matrix b)
{
    Matrix ans;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            ans.a[i][j]=0;
            for(int k=1;k<=2;k++)
            {
                ans.a[i][j]=max(ans.a[i][j],a.a[i][k]+b.a[k][j]);
            }
        }
    }
    return ans;
}
inline void add_edge(int from,int to)
{
    ed[++sz].to=to;
    ed[sz].next=head[from];
    head[from]=sz;
}
inline int read()
{
    char c=getchar();int x=0,flag=1;
    while(!isdigit(c)) flag*=c=='-'?-1:1,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*flag;
}
void dfs1(int u,int ff)
{
    size[u]=1;
    for(int i=head[u];i;i=ed[i].next)
    {
        int v=ed[i].to;
        if(v==ff) continue;
        deep[v]=deep[u]+1;
        fa[v]=u;
        dfs1(v,u);
        if(size[v]>size[son[u]])
        {
            son[u]=v;
        }
        size[u]+=size[v];
    }
}
void dfs2(int u,int ff,int tp)
{
    ind[u]=++tim;
    pre[tim]=u;
    top[u]=tp;
    if(!son[u])
    {
        bot[top[u]]=tim;
        return;
    }
    dfs2(son[u],u,tp);
    for(int i=head[u];i;i=ed[i].next)
    {
        int v=ed[i].to;
        if(v==ff||v==son[u]) continue;
        dfs2(v,u,v);
    }
}
void dp(int u,int ff)
{
    f[u][1]=w[u];
    g[u][1]=w[u];
    for(int i=head[u];i;i=ed[i].next)
    {
        int v=ed[i].to;
        if(v==ff) continue;
        dp(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
        if(v==son[u]) continue;
        g[u][0]+=max(f[v][0],f[v][1]);
        g[u][1]+=f[v][0];
    }
}
Matrix query(int root,int l,int r,int x,int y)
{
    if(x<=l&&y>=r) return t[root];
    int mid=l+r>>1;
    Matrix ans=I;
    if(y<=mid) return query(root<<1,l,mid,x,y);
    if(x>mid) return query(root<<1|1,mid+1,r,x,y);
    return query(root<<1,l,mid,x,y)*query(root<<1|1,mid+1,r,x,y);
}
Matrix get(int x)
{
    int A=ind[top[x]],B=bot[top[x]];
    return query(1,1,n,A,B);
}
void update(int root,int l,int r,int x)
{
    if(l==r)
    {
        t[root].a[1][1]=t[root].a[1][2]=g[pre[x]][0];
        t[root].a[2][1]=g[pre[x]][1];
        t[root].a[2][2]=0;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) update(root<<1,l,mid,x);
    else update(root<<1|1,mid+1,r,x);
    t[root]=t[root<<1]*t[root<<1|1];
}
void build(int root,int l,int r)
{
    if(l==r)
    {
        int tmp=pre[l];
        t[root].a[1][1]=t[root].a[1][2]=g[tmp][0];
        t[root].a[2][1]=g[tmp][1];
        t[root].a[2][2]=0;
        return;
    }
    int mid=l+r>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    t[root]=t[root<<1]*t[root<<1|1];
}
void modify(int x,int y)
{
    g[x][1]+=y-w[x];
    w[x]=y;
    while(x)
    {
        Matrix A=get(x);
        update(1,1,n,ind[x]);
        Matrix B=get(x);
        x=fa[top[x]];
        g[x][1]+=B.a[1][1]-A.a[1][1];
        g[x][0]+=max(B.a[1][1],B.a[2][1])-max(A.a[1][1],A.a[2][1]);
    }
}
int main()
{
    I.a[1][1]=I.a[2][2]=1;
    I.a[1][2]=I.a[2][1]=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }

    dfs1(1,1);
    dfs2(1,1,1);dp(1,1);
    build(1,1,n);
    while(m--)
    {
        int x=read(),y=read();
        modify(x,y);
        int a=ind[1],b=bot[1];
        Matrix tmp=query(1,1,n,a,b);
        cout<<max(tmp.a[1][1],tmp.a[2][1])<<'\n';
    }
    return 0;
}