动态dp

一、模板题：P4719 【模板】动态 DP：
题目描述
给定一棵n个点的树，点带点权。

有m次操作，每次操作给定x,y，表示修改点x的权值为y。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入格式
第一行，n,m，分别代表点数和操作数。

第二行，V1,V2,…,Vn，代表n个点的权值。

接下来n−1行，x,y，描述这棵树的n−1条边。

接下来m行，x,y，修改点x的权值为y。

输出格式
对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。

保证答案在int范围内

输入输出样例
输入 #1 复制
10 10
-11 80 -99 -76 56 38 92 -51 -34 47
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93
输出 #1 复制
186
186
190
145
189
288
244
320
258
304
说明/提示
对于30%的数据，1≤n,m≤10

对于60%的数据，1≤n,m≤1000

对于100%的数据，1≤n,m≤1e5

据说lct可以优化掉一个logn。咱也不会。
据说全局平衡二叉树也可以做。咱也没听过。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,m;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn],rk[maxn];
int top[maxn],id[maxn],vi[maxn],e[maxn];
int tot=1,cnt=0;
int dp[maxn][2];
struct ma
{
    int m[2][2];
};
ma g[maxn];

ma operator *(const ma &a,const ma &b)
{
    ma c;
    memset(c.m,0x80,sizeof(c.m));
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
                c.m[i][j]=max(c.m[i][j],a.m[i][k]+b.m[k][j]);
        }
    }
    return c;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int fa)
{
    int max_son=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        f[y]=x;
        d[y]=d[x]+1;

        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>max_son)max_son=si[y],son[x]=y;
    }
}

void dfs2(int x,int t)
{
    top[x]=t;id[x]=++cnt;
    rk[cnt]=x;e[t]=cnt;

    dp[x][0]=0,dp[x][1]=vi[x];
    g[x].m[0][0]=g[x].m[0][1]=0;
    g[x].m[1][0]=vi[x],g[x].m[1][1]=-inf;

    if(son[x])
    {
        dfs2(son[x],t);
        dp[x][0]+=max(dp[son[x]][0],dp[son[x]][1]);
        dp[x][1]+=dp[son[x]][0];
    }

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==son[x]||y==f[x]) continue;

        dfs2(y,y);

        dp[x][0]+=max(dp[y][0],dp[y][1]);
        dp[x][1]+=dp[y][0];
        g[x].m[0][0]+=max(dp[y][0],dp[y][1]);
        g[x].m[0][1]=g[x].m[0][0];
        g[x].m[1][0]+=dp[y][0];
    }
}

struct node
{
    int l,r;
    ma sum;
}t[maxn<<2];

void pushup(int cnt)
{
    t[cnt].sum=t[cnt<<1].sum*t[cnt<<1|1].sum;
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    if(l==r)
    {
        t[cnt].sum=g[rk[l]];
        return ;
    }

    int mid=(l+r)>>1;
    build(l,mid,cnt<<1);
    build(mid+1,r,cnt<<1|1);
    pushup(cnt);
}

void change(int x,int cnt)
{
    if(t[cnt].l==t[cnt].r)
    {
        t[cnt].sum=g[rk[x]];
        return ;
    }
    if(x<=t[cnt<<1].r) change(x,cnt<<1);
    else change(x,cnt<<1|1);
    pushup(cnt);
}


ma ask(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        return t[cnt].sum;
    }

    if(r<=t[cnt<<1].r) return ask(l,r,cnt<<1);
    else if(l>=t[cnt<<1|1].l) return ask(l,r,cnt<<1|1);
    else return ask(l,r,cnt<<1)*ask(l,r,cnt<<1|1);

}


void change_point(int x,int val)
{
    g[x].m[1][0]+=val-vi[x];
    vi[x]=val;
    ma pre,last;
    while(x)
    {
        pre=ask(id[top[x]],e[top[x]],1);
        change(id[x],1);
        last=ask(id[top[x]],e[top[x]],1);
        x=f[top[x]];
        g[x].m[0][0]+=max(last.m[0][0],last.m[1][0])-max(pre.m[0][0],pre.m[1][0]);
        g[x].m[0][1]=g[x].m[0][0];
        g[x].m[1][0]+=last.m[0][0]-pre.m[0][0];
    }
}


int main(void)
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&vi[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,cnt,1);

    ma ans;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        change_point(x,y);
        ans=ask(id[1],e[1],1);
        printf("%d\n",max(ans.m[0][0],ans.m[1][0]));
    }
    return 0;

}