动态dp初探

100 阅读 0 评论 66 点赞

我是靠谱客的博主秀丽羊，这篇文章主要介绍动态dp初探，现在分享给大家，希望可以做个参考。

动态dp初探

动态区间最大子段和问题

给出长度为(n)的序列和(m)次操作，每次修改一个元素的值或查询区间的最大字段和（SP1714 GSS3）。

设(f[i])为以下标(i)结尾的最大子段和，(g[i])表示从起始位置到(i)以内的最大子段和。
[ f[i]=max(f[i-1]+a[i],a[i])\g[i]=max(g[i-1],f[i]) ]
定义如下的矩阵乘法，显然这满足乘法结合律和分配律。
[ C=AB\C[i,j]=max_{k}(A[i,k]+B[k,j]) ]
将转移写为矩阵（注意(g[i]=max(g[i-1],f[i-1]+a[i],a[i]))）
[ begin{bmatrix} f[i]\ g[i]\ 0end{bmatrix} = begin{bmatrix} a[i]&-infty&a[i]\ a[i]&0&a[i]\ -infty&-infty&0end{bmatrix} begin{bmatrix} f[i-1]\ g[i-1]\ 0end{bmatrix} ]
可知每个元素(a[i])都对应了一个矩阵，可以认为区间([l,r])的答案所在矩阵正是
[ (prod_{i=l}^k begin{bmatrix} a[i]&-infty&a[i]\ a[i]&0&a[i]\ -infty&-infty&0 end{bmatrix} )begin{bmatrix} 0\ -infty\ 0end{bmatrix} ]
因此可以用线段树维护区间矩阵乘积。

复制代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[3][3];
    int*operator[](int d) {return a[d];}
    inline mtr() {}
    inline mtr(int val) {
        a[0][0]=a[0][2]=a[1][0]=a[1][2]=val;
        a[0][1]=a[2][0]=a[2][1]=-inf;
        a[1][1]=a[2][2]=0;
    }
    mtr operator*(mtr b) {
        static mtr c;
        memset(&c,-inf,sizeof c);
        for(int i=0; i<3; ++i) 
        for(int k=0; k<3; ++k) 
        for(int j=0; j<3; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} t,a[N<<2];

#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r) {
    if(l==r) {
        scanf("%d",&r);
        a[x]=mtr(r);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    a[x]=a[ls]*a[rs];
}
void modify(int x,int l,int r,int p,int val) {
    if(l==r) {
        a[x]=mtr(val);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) modify(ls,l,mid,p,val);
    else modify(rs,mid+1,r,p,val);
    a[x]=a[ls]*a[rs];
}
mtr query(int x,int l,int r,int L,int R) {
    if(L<=l&&r<=R) return a[x];
    int mid=(l+r)>>1;
    if(R<=mid) return query(ls,l,mid,L,R);
    if(mid<L) return query(rs,mid+1,r,L,R);
    return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R); 
}

int main() {
    memset(&t,-inf,sizeof t); //notice
    t[0][0]=t[2][0]=0;
    int n,q;
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&q);
    for(int op,l,r; q--; ) {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0) modify(1,1,n,l,r);
        else {
            mtr ret=query(1,1,n,l,r)*t;
            printf("%dn",max(ret[0][0],ret[1][0]));
        } 
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[3][3];
    int*operator[](int d) {return a[d];}
    inline mtr() {}
    inline mtr(int val) {
        a[0][0]=a[0][2]=a[1][0]=a[1][2]=val;
        a[0][1]=a[2][0]=a[2][1]=-inf;
        a[1][1]=a[2][2]=0;
    }
    mtr operator*(mtr b) {
        static mtr c;
        memset(&c,-inf,sizeof c);
        for(int i=0; i<3; ++i) 
        for(int k=0; k<3; ++k) 
        for(int j=0; j<3; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} t,a[N<<2];

#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r) {
    if(l==r) {
        scanf("%d",&r);
        a[x]=mtr(r);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    a[x]=a[ls]*a[rs];
}
void modify(int x,int l,int r,int p,int val) {
    if(l==r) {
        a[x]=mtr(val);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) modify(ls,l,mid,p,val);
    else modify(rs,mid+1,r,p,val);
    a[x]=a[ls]*a[rs];
}
mtr query(int x,int l,int r,int L,int R) {
    if(L<=l&&r<=R) return a[x];
    int mid=(l+r)>>1;
    if(R<=mid) return query(ls,l,mid,L,R);
    if(mid<L) return query(rs,mid+1,r,L,R);
    return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R); 
}

int main() {
    memset(&t,-inf,sizeof t); //notice
    t[0][0]=t[2][0]=0;
    int n,q;
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&q);
    for(int op,l,r; q--; ) {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0) modify(1,1,n,l,r);
        else {
            mtr ret=query(1,1,n,l,r)*t;
            printf("%dn",max(ret[0][0],ret[1][0]));
        } 
    }
    return 0;
}

动态树上最大权独立集

~~注意断句~~ 给出一棵(n)个节点树和(m)次操作，每次操作修改一个点权并计算当前树上的最大权独立集的权值。

重链剖分，设(y)为(x)的某个儿子，(s)是重儿子，(f[x,t])表示在以(x)为根的子树中不选/选(x)时的最大权独立集权值，(g[x,t])表示在以(x)的为根的子树中除去以(s)为根的子树部分内不选/选(x)的最大权独立集权值，。
[ g[x,0]=sum_{ynot=s}max(f[y,0],f[y,1])\ g[x,1]=a[x]+sum_{ynot=s} f[y,0]\ f[x,0]=g[x,0]+max(f[s,0],f[s,1])\ f[x,1]=g[x,1]+f[s,0] ]
然后改写为矩阵乘法
[ begin{bmatrix} f[x,0]\ f[x,1] end{bmatrix}= begin{bmatrix} g[x,0]&g[x,0]\ g[x,1]&-infty end{bmatrix} begin{bmatrix} f[s,0]\ f[s,1] end{bmatrix} ]
当(s)不存在时，钦定(f[s,0]=0)、(f[s,1]=-infty)。进一步可发现在一条链内，链顶的(f[,t])值正是链上所有的“G矩阵”（应该明白指的是那个吧）乘起来的第一列值。

因此我们可以树剖维护重链上这些矩阵的乘积，更新时从修改点跳到每条重链的链顶，计算链顶部(f[,t])，更新他父亲的(g[,t])（显然他不是父亲的重儿子）,然后再跳往父亲所在重链……。

也可以lct来做，~~（试了一下树剖发现麻烦爆了）~~每次access修改点到根，然后对这部分重计算就好了。

复制代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int d) {return a[d];}
    mtr() {memset(a,-inf,sizeof a);}
    mtr operator*(mtr b) {
        mtr c;
        for(int i=0; i<2; ++i) 
        for(int k=0; k<2; ++k) 
        for(int j=0; j<2; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} G[N],PG[N];

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int fa[N],ch[N][2],dp[N][2];

void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs(int x) {
    dp[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x;
        dfs(to[i]);
        dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
        dp[x][1]+=dp[to[i]][0];
    }
    G[x][0][0]=G[x][0][1]=dp[x][0];
    G[x][1][0]=dp[x][1];
    PG[x]=G[x];
} 
void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x]; //无交换律 
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int get(int x) {
    return ch[fa[x]][0]==x?0:(ch[fa[x]][1]==x?1:-1);
}
void rotate(int x) {
    int y=fa[x],k=get(x);
    if(~get(y)) ch[fa[y]][get(y)]=x;
    fa[x]=fa[y];
    fa[ch[y][k]=ch[x][k^1]]=y;
    fa[ch[x][k^1]=y]=x;
    update(y);
    update(x); 
}
void splay(int x) {
    while(~get(x)) {
        int y=fa[x];
        if(~get(y)) rotate(get(x)^get(y)?x:y);
        rotate(x);
    }
} 
void access(int x) {
    for(int y=0; x; x=fa[y=x]) {
        splay(x);
        if(ch[x][1]) { //旧的重儿子 
            G[x][0][0]+=max(PG[ch[x][1]][0][0],PG[ch[x][1]][1][0]);
            G[x][1][0]+=PG[ch[x][1]][0][0];
        }
        if(y) { //新的重儿子 
            G[x][0][0]-=max(PG[y][0][0],PG[y][1][0]);
            G[x][1][0]-=PG[y][0][0];
        }
        G[x][0][1]=G[x][0][0]; //别忘了 
        ch[x][1]=y;
        update(x);
    }
}
void modify(int x,int y) {
    access(x);
    splay(x);
    G[x][1][0]+=y-a[x];
    update(x);
    a[x]=y;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) scanf("%d",a+i);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1); //所有连边是轻边 
    for(int x,y; m--; ) {
        scanf("%d%d",&x,&y);
        modify(x,y);
        splay(1);
        printf("%dn",max(PG[1][0][0],PG[1][1][0]));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int d) {return a[d];}
    mtr() {memset(a,-inf,sizeof a);}
    mtr operator*(mtr b) {
        mtr c;
        for(int i=0; i<2; ++i) 
        for(int k=0; k<2; ++k) 
        for(int j=0; j<2; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} G[N],PG[N]; 

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int fa[N],ch[N][2],dp[N][2];

void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs(int x) {
    dp[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x;
        dfs(to[i]);
        dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
        dp[x][1]+=dp[to[i]][0];
    }
    G[x][0][0]=G[x][0][1]=dp[x][0];
    G[x][1][0]=dp[x][1];
    PG[x]=G[x];
} 
void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x]; //无交换律 
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int get(int x) {
    return ch[fa[x]][0]==x?0:(ch[fa[x]][1]==x?1:-1);
}
void rotate(int x) {
    int y=fa[x],k=get(x);
    if(~get(y)) ch[fa[y]][get(y)]=x;
    fa[x]=fa[y];
    fa[ch[y][k]=ch[x][k^1]]=y;
    fa[ch[x][k^1]=y]=x;
    update(y);
    update(x); 
}
void splay(int x) {
    while(~get(x)) {
        int y=fa[x];
        if(~get(y)) rotate(get(x)^get(y)?x:y);
        rotate(x);
    }
} 
void access(int x) {
    for(int y=0; x; x=fa[y=x]) {
        splay(x);
        if(ch[x][1]) { //旧的重儿子 
            G[x][0][0]+=max(PG[ch[x][1]][0][0],PG[ch[x][1]][1][0]);
            G[x][1][0]+=PG[ch[x][1]][0][0];
        }
        if(y) { //新的重儿子 
            G[x][0][0]-=max(PG[y][0][0],PG[y][1][0]);
            G[x][1][0]-=PG[y][0][0];
        }
        G[x][0][1]=G[x][0][0]; //别忘了 
        ch[x][1]=y;
        update(x);
    }
}
void modify(int x,int y) {
    access(x);
    splay(x);
    G[x][1][0]+=y-a[x];
    update(x);
    a[x]=y;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) scanf("%d",a+i);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1); //所有连边是轻边 
    for(int x,y; m--; ) {
        scanf("%d%d",&x,&y);
        modify(x,y);
        splay(1);
        printf("%dn",max(PG[1][0][0],PG[1][1][0]));
    }
    return 0;
}

全局平衡二叉树

然后讲一讲这道题的毒瘤加强版。传送门

数据加强并且经过特殊构造，树剖和LCT都过不了了。树剖本身复杂度太大， O((mlog^2n))过不了百万是很正常的；而LCT虽然只有一个(log) ，但由于常数过大也被卡了。

树剖的两个 (log) 基本上可以放弃治疗了。但是我们不禁要问，LCT究竟慢在哪里？

仔细想想，LCT的access复杂度之所以是一个 (log) ，是由于splay的势能分析在整棵LCT上依然成立，也就是说可以把LCT看作一棵大splay，在这棵大splay上的一次access只相当于一次splay。

话虽然是这么说，但是实际上当我们不停地随机access的时候，要调整的轻重链数量还是很多的。感受一下，拿极端情形来说，如果树是一条链，一开始全是轻边，那么对链末端的结点access一次显然应该是 (O(n))的。所以其实LCT的常数大就大在它是靠势能法得到的 (O(log n))，这么不靠谱的玩意是容易gg的。

但是如果我们不让LCT放任自由地access，而是一开始就给它构造一个比较优雅的姿态并让它静止（本来这棵树也不需要动），那么它也许就有救了。我们可以按照树链剖分的套路先划分出轻重边，然后对于重链建立一棵形态比较好的splay，至于轻儿子就跟原来的LCT一样直接用轻边挂上即可。什么叫“形态比较好”呢？我们给每个点 (x) 定义其权重为 size[x]-size[son[x]]，其中 son[x] 是它的重儿子，那么对于一条重链，我们可以先找到它的带权重心作为当前节点，然后对左右分别递归建树。

by GKxx blog

似乎较lct常数更小，也蛮好些的。

复制代码

#include <bits/stdc++.h> 
using namespace std;

namespace IO { // 卡着时限过
    const unsigned Buffsize=1<<24,Output=1<<24;
    static char Ch[Buffsize],*St=Ch,*T=Ch;
    inline char getc() {
        return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
    }
    static char Out[Output],*nowps=Out;
    inline void flush() {
        fwrite(Out,1,nowps-Out,stdout);
        nowps=Out;
    }
    template<typename T>inline void read(T&x) {
        x=0;
        static char ch;
        T f=1;
        for(ch=getc(); !isdigit(ch); ch=getc())if(ch=='-')f=-1;
        for(; isdigit(ch); ch=getc())x=x*10+(ch^48);
        x*=f;
    }
    template<typename T>inline void write(T x,char ch='n') {
        if(!x)*nowps++=48;
        if(x<0)*nowps++='-',x=-x;
        static unsigned sta[111],tp;
        for(tp=0; x; x/=10)sta[++tp]=x%10;
        for(; tp; *nowps++=sta[tp--]^48);
        *nowps++=ch;
        flush();
    }
}
using IO::read;
using IO::write;

const int N=1e6+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int x) {return a[x]; }
    inline mtr() {}
    inline mtr(int g0,int g1) {
        a[0][0]=a[0][1]=g0;
        a[1][0]=g1;
        a[1][1]=-inf;
    }
    inline mtr operator*(mtr b) {
        mtr c;
        c[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
        c[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
        c[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
        c[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
        return c;
    }
};

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int siz[N],son[N],g[N][2];
inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x,int pa) {
    siz[x]=1;
    g[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==pa) continue;
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
        g[x][0]+=max(g[to[i]][0],g[to[i]][1]);
        g[x][1]+=g[to[i]][0];
    }
}
void dfs2(int x,int pa) {
    if(!son[x]) return;
    g[x][0]-=max(g[son[x]][0],g[son[x]][1]);
    g[x][1]-=g[son[x]][0];
    for(int i=head[x]; i; i=last[i]) 
        if(to[i]!=pa) dfs2(to[i],x); 
}

mtr G[N],PG[N];
int root,fa[N],ch[N][2];
int stk[N],tp;
bool is_root[N];

inline void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x];
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int chain(int l,int r) {
    if(r<l) return 0;
    int sum=0,pre=0;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            int x=stk[i];
            ch[x][0]=chain(l,i-1);
            ch[x][1]=chain(i+1,r);
            if(ch[x][0]) fa[ch[x][0]]=x;
            if(ch[x][1]) fa[ch[x][1]]=x;
            update(x);
            return x;
        }
    }
    return 2333;
}
int tree(int top,int pa) {
    for(int x=top; x; x=son[pa=x]) {
        for(int i=head[x]; i; i=last[i]) {
            if(to[i]!=son[x]&&to[i]!=pa) {
                fa[tree(to[i],x)]=x;
            }
        } 
        G[x]=mtr(g[x][0],g[x][1]);
    }
    tp=0;
    for(int x=top; x; x=son[x]) stk[++tp]=x;
    return chain(1,tp);
}
inline void build() {
    root=tree(1,0);
    for(int i=1; i<=n; ++i) {
        is_root[i]=ch[fa[i]][0]!=i&&ch[fa[i]][1]!=i;
    }
}
inline int solve(int x,int y) {
    g[x][1]+=y-a[x];
    a[x]=y;
    for(int f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) { 
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
    return max(PG[root][0][0],PG[root][1][0]);
}

int main() {
    read(n);
    read(m);
    for(int i=1; i<=n; ++i) read(a[i]);
    for(int x,y,i=n; --i; ) {
        read(x);
        read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    int lastans=0;
    for(int x,y; m--; ) {
        read(x);
        read(y);
        x^=lastans;
        lastans=solve(x,y);
        write(lastans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h> 
using namespace std;

namespace IO { // 卡着时限过
    const unsigned Buffsize=1<<24,Output=1<<24;
    static char Ch[Buffsize],*St=Ch,*T=Ch;
    inline char getc() {
        return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
    }
    static char Out[Output],*nowps=Out;
    inline void flush() {
        fwrite(Out,1,nowps-Out,stdout);
        nowps=Out;
    }
    template<typename T>inline void read(T&x) {
        x=0;
        static char ch;
        T f=1;
        for(ch=getc(); !isdigit(ch); ch=getc())if(ch=='-')f=-1;
        for(; isdigit(ch); ch=getc())x=x*10+(ch^48);
        x*=f;
    }
    template<typename T>inline void write(T x,char ch='n') {
        if(!x)*nowps++=48;
        if(x<0)*nowps++='-',x=-x;
        static unsigned sta[111],tp;
        for(tp=0; x; x/=10)sta[++tp]=x%10;
        for(; tp; *nowps++=sta[tp--]^48);
        *nowps++=ch;
        flush();
    }
}
using IO::read;
using IO::write;

const int N=1e6+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int x) {return a[x]; }
    inline mtr() {}
    inline mtr(int g0,int g1) {
        a[0][0]=a[0][1]=g0;
        a[1][0]=g1;
        a[1][1]=-inf;
    }
    inline mtr operator*(mtr b) {
        mtr c;
        c[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
        c[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
        c[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
        c[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
        return c;
    }
};

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int siz[N],son[N],g[N][2];
inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x,int pa) {
    siz[x]=1;
    g[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==pa) continue;
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
        g[x][0]+=max(g[to[i]][0],g[to[i]][1]);
        g[x][1]+=g[to[i]][0];
    }
}
void dfs2(int x,int pa) {
    if(!son[x]) return;
    g[x][0]-=max(g[son[x]][0],g[son[x]][1]);
    g[x][1]-=g[son[x]][0];
    for(int i=head[x]; i; i=last[i]) 
        if(to[i]!=pa) dfs2(to[i],x); 
}

mtr G[N],PG[N];
int root,fa[N],ch[N][2];
int stk[N],tp;
bool is_root[N];

inline void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x];
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int chain(int l,int r) {
    if(r<l) return 0;
    int sum=0,pre=0;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            int x=stk[i];
            ch[x][0]=chain(l,i-1);
            ch[x][1]=chain(i+1,r);
            if(ch[x][0]) fa[ch[x][0]]=x;
            if(ch[x][1]) fa[ch[x][1]]=x;
            update(x);
            return x;
        }
    }
    return 2333;
}
int tree(int top,int pa) {
    for(int x=top; x; x=son[pa=x]) {
        for(int i=head[x]; i; i=last[i]) {
            if(to[i]!=son[x]&&to[i]!=pa) {
                fa[tree(to[i],x)]=x;
            }
        } 
        G[x]=mtr(g[x][0],g[x][1]);
    }
    tp=0;
    for(int x=top; x; x=son[x]) stk[++tp]=x;
    return chain(1,tp);
}
inline void build() {
    root=tree(1,0);
    for(int i=1; i<=n; ++i) {
        is_root[i]=ch[fa[i]][0]!=i&&ch[fa[i]][1]!=i;
    }
}
inline int solve(int x,int y) {
    g[x][1]+=y-a[x];
    a[x]=y;
    for(int f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) { 
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
    return max(PG[root][0][0],PG[root][1][0]);
}

int main() {
    read(n);
    read(m);
    for(int i=1; i<=n; ++i) read(a[i]);
    for(int x,y,i=n; --i; ) {
        read(x);
        read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    int lastans=0;
    for(int x,y; m--; ) {
        read(x);
        read(y);
        x^=lastans;
        lastans=solve(x,y);
        write(lastans);
    }
    return 0;
}

NOIP18 保卫王国

给出一棵(n)个节点树和(m)次询问，每次询问强制选/不选两个点然后计算当前树上的最小覆盖集，询问互相独立。

提示：强制选一个点就是把它的点权改成0，强制不选就是改成 (infty)；最小覆盖权值+最大独立集权值=总权值。

复制代码

// 省略了一些函数
// O2下速度还不错
// 注意long long
const int N=1e6+10;
const long long inf=1e10;

......
    
long long tot,res;
inline void solve(int x,long long y) {
    tot+=y;
    g[x][1]+=y;
    for(long long f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) {
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
}
inline void solve(int x,int p,int y,int q) {
    long long sx,sy;
    if(!p&&!q) sx=inf,sy=inf,res=0;
    else if(!p&&q) sx=inf,sy=0,res=a[y];
    else if(p&&!q) sx=0,sy=inf,res=a[x];
    else sx=0,sy=0,res=a[x]+a[y];
    solve(x,sx-a[x]);
    solve(y,sy-a[y]);
    res+=tot-max(PG[root][0][0],PG[root][1][0]);
    solve(x,a[x]-sx);
    solve(y,a[y]-sy);
}

char type[10]; 
int main() {
    scanf("%d%d%s",&n,&m,type);
    for(int i=1; i<=n; ++i) {
        scanf("%lld",a+i);
        tot+=a[i];
    }
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    for(int x,p,y,q; m--; ) {
        scanf("%d%d%d%d",&x,&p,&y,&q);
        if(!p&&!q&&(prt[x]==y||prt[y]==x)) {
            puts("-1");
            continue;
        }
        solve(x,p,y,q);
        printf("%lldn",res);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 省略了一些函数
// O2下速度还不错
// 注意long long
const int N=1e6+10;
const long long inf=1e10;

......
    
long long tot,res;
inline void solve(int x,long long y) {
    tot+=y;
    g[x][1]+=y;
    for(long long f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) {
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
}
inline void solve(int x,int p,int y,int q) {
    long long sx,sy;
    if(!p&&!q) sx=inf,sy=inf,res=0;
    else if(!p&&q) sx=inf,sy=0,res=a[y];
    else if(p&&!q) sx=0,sy=inf,res=a[x];
    else sx=0,sy=0,res=a[x]+a[y];
    solve(x,sx-a[x]);
    solve(y,sy-a[y]);
    res+=tot-max(PG[root][0][0],PG[root][1][0]);
    solve(x,a[x]-sx);
    solve(y,a[y]-sy);
}

char type[10]; 
int main() {
    scanf("%d%d%s",&n,&m,type);
    for(int i=1; i<=n; ++i) {
        scanf("%lld",a+i);
        tot+=a[i];
    }
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    for(int x,p,y,q; m--; ) {
        scanf("%d%d%d%d",&x,&p,&y,&q);
        if(!p&&!q&&(prt[x]==y||prt[y]==x)) {
            puts("-1");
            continue;
        }
        solve(x,p,y,q);
        printf("%lldn",res);
    }
    return 0;
}

bzoj4911 [Sdoi2017]切树游戏

留坑。

bzoj4721 洪水

给出一棵(n)个节点的树以及(m)次操作，每次操作修改删除某一个点的代价，或者查询删除一些点使得节点(x)不与其子树中任意叶节点联通的最小代价和。

重链剖分，设(y)为(x)的某个儿子，(s)是重儿子，(f[x])表示在以(x)为根的子树时的解，(g[x]=sum_{ynot=s}f[y])。当(x)是叶节点时，(g[x]=+infty)，(f[x]=a[x])。一般转移为(f[x]=min(a[x],g[x]+f[s]))。

使用变换(T(a,b)(v))表示一个转移(min(a,v+b))，变换的合并为
[ begin{aligned} T(a,b)(T(c,d)(v)) &=min(a,min(c,v+d)+b)\ &=min(a,c+b,v+d+b)&(star)\ &=min(min(a,c+b),v+(d+b))\ &=T(min(a,c+b),d+b)(v) end{aligned} ]
思考((star))的意义。同“动态树上最大权独立集”类似的处理，节点(x)对应着一个变换(T(a[x],g[x])(v))，那么子树(x)的答案(f[x])为(x)到(x)所在重链的底上所有变换从后往前的并作用在(0)上的值。

仍然使用全局平衡二叉树来维护。

~~来自copier的怨念~~

关于统计答案，首先得知道辅助树上(ch[x,1])指向(x)管辖范围([l,r])内的后一半即([x+1,r])这一段，所以我们可以从(x)出发，记录(R)为已经得到了([x,R])的贡献，加上(ch[x,1])这段的贡献，然后不断跳(fa[x])直到(x=R+1)，接着统计并更新(R)。当(R)到达链底时结束。

一个巧妙地实现是不需要记录(R)，每次在链内向上跳(fa[x])时，如果(ch[fa[x],0]==x)，就统计(ch[fa[x],1])地贡献。显然这样也能达到同样的效果。

再补充。0看作时所有叶子节点的轻儿子，设其中一个叶子节点为(l)。
[ text{set} begin{cases} g[0]=0\ a[0]=+infty\ f[0]=+infty\ end{cases} rightarrow begin{cases} g[l]=f[0]=+infty\ f[l]=min(a[l],0+g[l])=a[l] end{cases} ]

所以强令(a[0]=f[0]=+infty)，就能使所有的叶子节点初始化。

关于答案输出需要留意每个叶子节点的第二个参数是(+infty)结合变换合并的公式可知最终得到的合变换内第二个参数无穷大，所以答案是第一个参数。

复制代码

#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int N=1e6+10;
const LL inf=1e14;

struct trans {
    LL a,b;
    inline trans() {}
    inline trans(LL a,LL b):a(a),b(b){}
    inline trans calc(trans t) {
        return trans(min(a,t.a+b),t.b+b);
    }
} T[N],PT[N];

int n,m;
LL a[N],f[N];
int siz[N],son[N],head[N],to[N<<1],last[N<<1];

inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
int ch[N][2],fa[N],stk[N],tp;
bool irt[N];
inline void update(int x) {
    PT[x]=PT[ch[x][0]].calc(T[x].calc(PT[ch[x][1]]));
}
int chain(int l,int r) {
    if(l>r) return 0;
    int sum=0,pre=0,x;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            x=stk[i];
            fa[ch[x][0]=chain(l,i-1)]=x;
            fa[ch[x][1]=chain(i+1,r)]=x;
            update(x);
            break;
        }
    }
    return x;
}
int build(int x) {
    for(tp=0; x; x=son[x]) stk[++tp]=x;
    irt[x=chain(1,tp)]=1;
    return x;  
}
void dfs(int x) {
    siz[x]=1;
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x;
        dfs(to[i]); 
        f[x]+=f[to[i]];
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
    }
    if(son[x]) {
        T[x]=trans(a[x],f[x]-f[son[x]]);
        f[x]=min(f[x],a[x]);
    } else {
        T[x]=trans(a[x],inf);
        f[x]=a[x];
    }
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]!=fa[x]&&to[i]!=son[x]) 
            fa[build(to[i])]=x;
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%lld",a+i);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    PT[0]=trans(inf,0); //
    dfs(1), fa[build(1)]=0;
  /*for(int i=0; i<=n; ++i) 
    cout<<T[i].a<<' '<<T[i].b<<' '<<PT[i].a<<' '<<PT[i].b<<endl;
    cout<<endl;
    */  
    scanf("%d",&m);
    while(m--) {
        static char op[10];
        static int x,y;
        scanf("%s%d",op,&x);
        if(op[0]=='Q') {
            trans ans=T[x].calc(PT[ch[x][1]]);
            for(; !irt[x]; x=fa[x]) {
                if(ch[fa[x]][0]==x) ans=ans.calc(T[fa[x]].calc(PT[ch[fa[x]][1]]));
            }
            printf("ans is %lldn",ans.a);
        } else {
            scanf("%d",&y);
            T[x].a+=y;
            for(; x; x=fa[x]) {
                if(irt[x]) T[fa[x]].b-=PT[x].a;
                update(x);
                if(irt[x]) T[fa[x]].b+=PT[x].a;
            }
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int N=1e6+10;
const LL inf=1e14;

struct trans {
    LL a,b;
    inline trans() {}
    inline trans(LL a,LL b):a(a),b(b){}
    inline trans calc(trans t) {
        return trans(min(a,t.a+b),t.b+b);
    }
} T[N],PT[N];

int n,m;
LL a[N],f[N];
int siz[N],son[N],head[N],to[N<<1],last[N<<1];

inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
int ch[N][2],fa[N],stk[N],tp;
bool irt[N];
inline void update(int x) {
    PT[x]=PT[ch[x][0]].calc(T[x].calc(PT[ch[x][1]]));
}
int chain(int l,int r) {
    if(l>r) return 0;
    int sum=0,pre=0,x;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            x=stk[i];
            fa[ch[x][0]=chain(l,i-1)]=x;
            fa[ch[x][1]=chain(i+1,r)]=x;
            update(x);
            break;
        }
    }
    return x;
}
int build(int x) {
    for(tp=0; x; x=son[x]) stk[++tp]=x;
    irt[x=chain(1,tp)]=1;
    return x;  
}
void dfs(int x) {
    siz[x]=1;
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x;
        dfs(to[i]); 
        f[x]+=f[to[i]];
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
    }
    if(son[x]) {
        T[x]=trans(a[x],f[x]-f[son[x]]);
        f[x]=min(f[x],a[x]);
    } else {
        T[x]=trans(a[x],inf);
        f[x]=a[x];
    }
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]!=fa[x]&&to[i]!=son[x]) 
            fa[build(to[i])]=x;
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%lld",a+i);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    PT[0]=trans(inf,0); //
    dfs(1), fa[build(1)]=0;
  /*for(int i=0; i<=n; ++i) 
    cout<<T[i].a<<' '<<T[i].b<<' '<<PT[i].a<<' '<<PT[i].b<<endl;
    cout<<endl;
    */  
    scanf("%d",&m);
    while(m--) {
        static char op[10];
        static int x,y;
        scanf("%s%d",op,&x);
        if(op[0]=='Q') {
            trans ans=T[x].calc(PT[ch[x][1]]);
            for(; !irt[x]; x=fa[x]) {
                if(ch[fa[x]][0]==x) ans=ans.calc(T[fa[x]].calc(PT[ch[fa[x]][1]]));
            }
            printf("ans is %lldn",ans.a);
        } else {
            scanf("%d",&y);
            T[x].a+=y;
            for(; x; x=fa[x]) {
                if(irt[x]) T[fa[x]].b-=PT[x].a;
                update(x);
                if(irt[x]) T[fa[x]].b+=PT[x].a;
            }
        }
    }
    return 0;
}