问题一

考虑带修改最大子段和的问题:

给一个序列,支持

  1. 求最大子段和
  2. 单点修改

求最大子段和有这样一个贪心做法,即遍历序列,令

让我们定义一种新的矩阵运算方式:。因此我们可以得到

这样最后的答案其实是(不是直接取,因为多算了一次),初始矩阵

由于矩阵运算具有结合律,因此线段树维护矩阵快速幂同样可以解决本问题。

问题二

考虑带修改带点权树上最大权独立集问题:

给出一棵带点权有根树,支持:

  1. 修改点权;
  2. 询问一棵子树的最大权独立集。

考虑暴力 DP,表示以为根的子树,是()否()在独立集中,的最大权独立集。容易得到

可以将转移式等价地写作

将树链剖分,转化为链上的问题。假设重链上从浅到深第个结点的编号是,且令

表示它的轻儿子的 DP 值,则有

丢到里面去就能写成矩乘的形式了:

这样,这条重链的矩阵就是它轻儿子的 DP 值了。单点修改的时候,沿着链往上跳,并修改对应的

#include<algorithm>
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
/******************heading******************/
#define int lld
const int N=1e5+5,MTX=2,INF=0x3f3f3f3f,LST=N<<2;

int n,m;
int val[N];

struct qxx{int nex,t;};
qxx e[N*2];
int h[N],le;
void add_path(int f,int t){e[++le]=(qxx){h[f],t},h[f]=le;}

struct mtx{/*{{{*/
    int r,c;
    int w[MTX][MTX];
    mtx(){
        r=c=0;
    }
    mtx(int _r,int _c){
        r=_r,c=_c;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=-INF;
    }
    mtx(int _r){
        r=c=_r;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=i==j?0:-INF;
    }
    mtx(int _r,int _c,int _w[MTX][MTX]){
        r=_r,c=_c;
        FOR(i,0,r-1)FOR(j,0,c-1)w[i][j]=_w[i][j];
    }
    mtx operator*(mtx m){
        //assert(c==m.r);
        mtx res(r,m.c);
        FOR(i,0,r-1)FOR(j,0,m.c-1)FOR(k,0,c-1)
            res.w[i][j]=max(res.w[i][j],w[i][k]+m.w[k][j]);
        return res;
    }
    mtx operator*=(mtx m){ return *this=*this*m; }
    void print(){
        FOR(i,0,r-1){
            printf("|");
            FOR(j,0,c-1)if(w[i][j]==-INF)printf("-INF");else printf("%3lld ",w[i][j]);
            printf("|");
            puts("");
        }
        puts("");
    }
};/*}}}*/

mtx tree_mt[N];
int totdfn;

namespace seg{
    mtx mt[LST];
    void pushup(int u){
        mt[u]=mt[u<<1]*mt[u<<1|1];//left multiply
    }
    void build(int u=1,int l=1,int r=totdfn){
        if(l==r)return mt[u]=tree_mt[l],void();
        int mid=(l+r)>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
    mtx query(int L,int R,int u=1,int l=1,int r=totdfn){
        if(L<=l&&r<=R)return mt[u];
        int mid=(l+r)>>1;
        mtx res(MTX);
        if(L<=mid)res*=query(L,R,u<<1,l,mid);
        if(mid<R)res*=query(L,R,u<<1|1,mid+1,r);
        return res;
    }
    void assign(int p,mtx matrix,int u=1,int l=1,int r=totdfn){
        if(l==r)return mt[u]=matrix,void();
        int mid=(l+r)>>1;
        if(p<=mid)assign(p,matrix,u<<1,l,mid);
        else assign(p,matrix,u<<1|1,mid+1,r);
        pushup(u);
    }
}

int dep[N],hvs[N],sz[N],tp[N],bt[N],fa[N],dfn[N];
int f[N][2],g[N][2];
int dfs1(int u,int p){/*{{{*/
    dep[u]=dep[p]+1,sz[u]=1;
    fa[u]=p;
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        sz[u]+=dfs1(v,u);
    }
    return sz[u];
}/*}}}*/
void dfs2(int u,int p,int to){/*{{{*/
    tp[u]=to,bt[u]=u,dfn[u]=++totdfn;
    int mx=0;
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        if(sz[v]>mx)mx=sz[v],hvs[u]=v;
    }
    if(hvs[u])dfs2(hvs[u],u,to),bt[u]=bt[hvs[u]];
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p||v==hvs[u])continue;
        dfs2(v,u,v);
    }
    //printf("u=%lld,hvs=%lld,tp=%lld,bt=%lld\n",u,hvs[u],tp[u],bt[u]);
}/*}}}*/
void dfs3(int u,int p){
    for(int i=h[u];i;i=e[i].nex){
        const int v=e[i].t;
        if(v==p)continue;
        dfs3(v,u);
        if(v!=hvs[u]) g[u][0]+=max(f[v][0],f[v][1]), g[u][1]+=f[v][0];
        else f[u][0]=max(f[v][0],f[v][1]), f[u][1]=f[v][0];
    }
    g[u][1]+=val[u];
    f[u][0]+=g[u][0],f[u][1]+=g[u][1];
    //printf("u=%-2d,f0=%-3d,f1=%-4d,g0=%-3d,g1=%-3d\n",u,f[u][0],f[u][1],g[u][0],g[u][1]);
    int t[MTX][MTX]={g[u][0],g[u][0],g[u][1],-INF};
    tree_mt[dfn[u]]=mtx(2,2,t);
    //tree_mt[dfn[u]].print();
}

mtx f_mtx(int u){//calculate f[u][0],f[u][1] -> g_mtx[0][0],g_mtx[1][0]
    return seg::query(dfn[u],dfn[bt[u]]);
}
void assign(int u,int v){//val[u]=v
    //printf("assign(%lld,%lld)\n",u,v);
    g[u][1]=g[u][1]-val[u]+v,val[u]=v;
    while(u){
        //printf("u=%lld\n",u);
        int t[MTX][MTX]={g[u][0],g[u][0],g[u][1],-INF};
        seg::assign(dfn[u],mtx(2,2,t));
        u=tp[u];
        mtx a=f_mtx(u);// 当前链顶的 f
        if(fa[u]){
            g[fa[u]][1]=g[fa[u]][1]-f[u][0]+a.w[0][0];
            g[fa[u]][0]=g[fa[u]][0]-max(f[u][0],f[u][1])+max(a.w[0][0],a.w[1][0]);
        }
        f[u][0]=a.w[0][0],f[u][1]=a.w[1][0];
        u=fa[u];
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n)scanf("%lld",&val[i]);
    FOR(i,1,n-1){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add_path(x,y),add_path(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    dfs3(1,0);
    seg::build();
    FOR(i,1,m){
        int x,y;
        scanf("%lld%lld",&x,&y);
        assign(x,y);
        mtx ans=f_mtx(1);
        printf("%lld\n",max(ans.w[0][0],ans.w[1][0]));
    }
    return 0;
}
/*
 * g[u,0]=sum_{v!=hvs[u]} max(f[v,0],f[v,1])
 * g[u,1]=a[u] + sum_{v!=hvs[u]} f[v,0]
 * f[u,0]=g[u,0]+max(f[u+1,0],f[u+1,1])
 * f[u,1]=g[u,1]+f[u+1,0]
 * f[leaf,0]=g[leaf,0]=0
 * f[leaf,1]=g[leaf,1]=a[leaf]
 */

问题三

带点权的有根树上,选择一个点可以覆盖它子树的叶子结点。问覆盖某个子树的叶子结点的最小代价。单点修改

朴素的 DP 是

则得到

于是得到

问题四

n 个人进行轮游戏,第轮第个人可以选择让。初始时,游戏从编号为 0 的人开始。游戏结束后第个人获胜。对于第个人,只有当变了后必胜,不变不必胜的时候才会选择变,并且这是一个 Common Knowledge。支持单点修改,问谁获胜。

手玩发现,只有当时,第个人才可能会动。因为每个人都只会想自己赢,不会把别人送赢。因此不能指望后面的人帮他把变成。由此可以推出,如果,则不可能获胜。因为前面的只会把变成自己,不会变得比自己大。于是我们想到连边,这样可以构成一棵树,显然编号为的点是根结点。

沿着树边走到结点,相当于选择变,把从上一个结点编号变成了。于是我们定义表示最优策略下是否会动。则显然当的儿子结点都不动时,选择动是必胜的:

若根结点为则根结点获胜。否则沿着它编号最小的儿子往下走,第一个的点获胜。如果整颗树的 DP 值都是则根结点也获胜。单点修改相当于修改某个点的父亲,则 LCT 维护动态 DP 即可。