「bzoj5210」最大连通子块和 - 树链剖分维护树形动规 | Bill Yang's Blog

「bzoj5210」最大连通子块和 - 树链剖分维护树形动规

题目大意

    给出一棵$n$个点、以$1$为根的有根树,点有点权。要求支持如下两种操作:

  • $M \ x \ y$:将点$x$的点权改为$y$;
  • $Q \ x$:求以$x$为根的子树的最大连通子块和。

    其中,一棵子树的最大连通子块和指的是:该子树所有子连通块的点权和中的最大值。
    (本题中子连通块包括空连通块,点权和为$0$)。


题目分析

今天早上一看,BZOJ里多了几道题,全部都写着“本OJ版权所有,翻版必究”,BZOJ强无敌啊

看一眼就知道是树链剖分维护动态DP的题,不会的搜索我的学习笔记吧。
先设状态$f(i)$表示以$i$为根的子树中,选择包含$i$的最大连通子块和(可以选择空集),$g(i)$表示以$i$为根的子树中的最大连续子块和,用$\rm{child}(i)$表示$i$的儿子集合,用$\rm{son}(i)$(省略为$son$)表示$i$的重儿子。

将方程拆分出重儿子:

令$\sum_{j\in\rm{child}(i),j\neq son}f(j)=\rm{restf}(i)$,$\max_{j\in\rm{child}(i),j\neq son}\lbrace g(j)\rbrace=\rm{restg}(i)$。

则转移方程可以看作是对重儿子作线性变换。
不妨用矩阵来表示转移。
重新定义乘法表示相加,加法表示取两者的$\max$。
不难证明其仍满足结合律。

这样就已经可以暴力套用矩阵乘法,只是常数稍大,不过应该是可以过的。
为了优化常数,考虑对转移矩阵进行结合。

除了$a,b,c,d$项其它元素都没变。
故我们只需要维护这四个变量即可。
矩阵初值:$a=\rm{restf}(x)+v_x,b=\rm{restf}(x)+v_x,c=0,d=\rm{restg}[x]$
向量单位元:$\begin{pmatrix} 0 & 0 & 0 & 0 \end{pmatrix}$
根据单位元,可以通过矩阵的$\max(a,c,0)$得到$f$,通过$\max(b,d,0)$得到$g$。

然后线段树合并就好了。
每次修改的时候按套路从底往上修改,每次去除原有影响加入新影响。
$\rm{restf}$可以直接更新,$\rm{restg}$需要维护一个可删除堆。


代码

代码中的$f[]$为$\rm{restf}[]$,$g[]$为$\rm{restg}[]$。使用$\text{get_f}(),\text{get_g}()$来获取真正的$f,g$值。
目前此代码拿了bzoj rank1,估计不久就会被顶下去吧。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=200005;
int n,m,step=0,root[maxn],pos[maxn],father[maxn],Depth[maxn],Size[maxn],Son[maxn],Top[maxn],Dfn[maxn];
LL f[maxn],val[maxn];
vector<int> edges[maxn],chain[maxn],tops;
void Dfs1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Son[Now]]<Size[Next])Son[Now]=Next;
}
}
void Dfs2(int Now,int top) {
Top[Now]=top;
Dfn[Now]=++step;
chain[top].push_back(Now);
if(Now==top)tops.push_back(top);
if(Son[Now])Dfs2(Son[Now],top);
for(int Next:edges[Now]) {
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}
bool cmp(int x,int y) {return Depth[x]>Depth[y];}
struct Heap {
priority_queue<LL> add,del;
void push(LL x) {add.push(x);}
void erase(LL x) {del.push(x);}
LL top() {
while(!del.empty()&&add.top()==del.top())add.pop(),del.pop();
return !add.empty()?add.top():0;
}
} g[maxn];
struct Tag {
LL a,b,c,d;
Tag(LL a=0,LL b=0,LL c=0,LL d=0):a(a),b(b),c(c),d(d) {}
LL f() {return max(max(a,c),0ll);}
LL g() {return max(max(b,d),0ll);}
Tag operator + (const Tag &y) const {
Tag ans;
ans.a=a+y.a;
ans.b=max(a+y.b,b);
ans.c=max(max(c+y.a,y.c),0ll);
ans.d=max(max(max(c+y.b,d),y.d),0ll);
return ans;
}
};
struct Segment_Tree {
struct Tree {
int left,right;
int lson,rson;
Tag tag;
Tree(int l=0,int r=0):left(l),right(r) {lson=rson=0;}
} tree[maxn<<2];
#define ls tree[index].lson
#define rs tree[index].rson
void build(int &index,int Left,int Right,int top) {
if(!index)index=++step;
tree[index]=Tree(Left,Right);
if(Left==Right) {
int x=chain[top][Left-1];
tree[index].tag=Tag(f[x]+val[x],f[x]+val[x],0,g[x].top());
pos[x]=Left;
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,top);
build(rs,mid+1,Right,top);
push_up(index);
}
void push_up(int index) {tree[index].tag=tree[rs].tag+tree[ls].tag;}
void modify(int index,int tar,Tag v) {
if(tar<tree[index].left||tar>tree[index].right)return;
if(tree[index].left==tree[index].right) {tree[index].tag=v;return;}
modify(ls,tar,v);
modify(rs,tar,v);
push_up(index);
}
Tag query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].tag;
return query(rs,Left,Right)+query(ls,Left,Right);
}
} st;
LL get_f(int x) {return st.query(root[Top[x]],pos[x],chain[Top[x]].size()).f();}
LL get_g(int x) {return st.query(root[Top[x]],pos[x],chain[Top[x]].size()).g();}
void Modify(int x,int v) {
val[x]=v;
for(int t; father[t=Top[x]]; x=father[t]) {
Tag last=st.tree[root[t]].tag;
st.modify(root[t],pos[x],Tag(f[x]+val[x],f[x]+val[x],0,g[x].top()));
f[father[t]]+=-last.f()+st.tree[root[t]].tag.f();
g[father[t]].erase(last.g()),g[father[t]].push(st.tree[root[t]].tag.g());
}
st.modify(root[Top[x]],pos[x],Tag(f[x]+val[x],f[x]+val[x],0,g[x].top()));
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)val[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
edges[x].push_back(y);
edges[y].push_back(x);
}
Dfs1(1,0,1);
Dfs2(1,1);
sort(tops.begin(),tops.end(),cmp);
for(int x:tops) {
st.build(root[x],1,chain[x].size(),x);
if(father[x]) {
f[father[x]]+=st.tree[root[x]].tag.f();
g[father[x]].push(st.tree[root[x]].tag.g());
}
}
while(m--) {
int opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int();
if(opt=='M')Modify(x,Get_Int());
else printf("%lld\n",get_g(x));
}
return 0;
}

0%