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

题目大意

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

$M \ x \ y$：将点$x$的点权改为$y$；

$Q \ x$：求以$x$为根的子树的最大连通子块和。

其中，一棵子树的最大连通子块和指的是：该子树所有子连通块的点权和中的最大值。
（本题中子连通块包括空连通块，点权和为$0$）。

题目分析

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

$f(i)=\max(0,\sum_{j\in\rm{child}(i)}f(j)+v_i)$ $g(i)=\max(\max_{j\in\rm{child}(i)}\lbrace g(j)\rbrace,f(i))$

将方程拆分出重儿子：

$f(i)=\max(0,f(\rm{son})+\sum_{j\in\rm{child}(i),j\neq son}f(j)+v_i)$ $g(i)=\max(g(\rm{son}),\max_{j\in\rm{child}(i),j\neq son}\lbrace g(j)\rbrace,f(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$。
不难证明其仍满足结合律。

$\begin{pmatrix} f(i) & g(i) & 0 & 0 \end{pmatrix}=\begin{pmatrix} f(son) & g(son) & 0 & 0 \end{pmatrix}\times\begin{bmatrix} \rm{restf}(i)+v_i & \rm{restf}(i)+v_i & -inf & -inf \\ -inf & 0 & -inf & -inf \\ 0 & \rm{restg}(x) & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

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

$\begin{aligned}&\begin{bmatrix} a_1 & b_1 & -inf & -inf \\ -inf & 0 & -inf & -inf \\ c_1 & d_1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} a_2 & b_2 & -inf & -inf \\ -inf & 0 & -inf & -inf \\ c_2 & d_2 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ =&\begin{bmatrix} a_1+a_2 & \max(a_1+b_2,b_1) & -inf & -inf \\ -inf & 0 & -inf & -inf \\ \max(c_1+a_2,c_2,0) & \max(c_1+b_2,d_1,d_2,0) & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\end{aligned}$

除了$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，估计不久就会被顶下去吧。

#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;
}