【BZOJ5210】最大连通子块和

Description

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

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

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

其中，一棵子树的最大连通子块和指的是：该子树所有子连通块的点权和中的最大值

（本题中子连通块包括空连通块，点权和为0）。

Input

第一行两个整数n、m，表示树的点数以及操作的数目。

第二行n个整数，第i个整数w_i表示第i个点的点权。

接下来的n-1行，每行两个整数x、y，表示x和y之间有一条边相连。

接下来的m行，每行输入一个操作，含义如题目所述。保证操作为M x y或Q x之一。

1≤n,m≤200000 ，任意时刻 |w_i|≤10^9 。

Output

对于每个Q操作输出一行一个整数，表示询问子树的最大连通子块和。

Sample Input

5 4
3 -2 0 3 -1
1 2
1 3
4 2
2 5
Q 1
M 4 1
Q 1
Q 2

Sample Output

4
3
1

题解：首先思路源自WC2018上陈俊锟所说的动态DP。

$O(n^2)$做法：

我们考虑每次询问时都进行一次树形DP。我们令f[x]表示x子树中，包含x的连通块的权值和最大值(可以为空)，容易得到DP方程：$f[x]=max(0,v[x]+\sum f[y])$（y是x的儿子）。再维护s[x]表示x的子树中连通块的权值和最大值，$s[x]=max(f[x],s[y]) $。如果每次询问都进行一次树形DP的话，修改的复杂度是O(1)，查询的复杂度是O(x的子树大小)。但是我们发现每次修改时只会对x到根这一条链上的点的DP值造成影响，其中对f[]的影响可以直接加减得到，对s[]的影响我们可以通过对每个点都开一个可删除堆维护。这样一来查询的复杂就变成了O(1)，但是修改的复杂度变成了O(x的深度*log n)，依然无法通过此题。

$O(n\log^2n)$做法：

我们考虑优化上面说的第二种暴力，不难想到用树剖+线段树来维护。我们令$g[x]=\sum f[y] $(y是x的轻儿子)。那么重链上的转移就变成了$f[x]=max(0,f[son[x]]+g[x])$。你会惊讶的发现这个式子就是最大连续子段和的形式！所以在修改时，我们从x沿着不断往根跳，对于重链，在线段树上维护g[x]的最大连续子段和；对于轻链，暴力维护DP值即可。

接下来考虑如何维护s[]。我们沿用上面的思路，对每个点维护一个可删除堆，但是这里的堆维护的是x的所有轻儿子的s值，重儿子的s值我们放到线段树上同最大连续子段和一起维护（代码中记为sm，表示max(g值的最大连续子段和,所有点的轻儿子的s)）。那么我们在线段树上更新时，只需要用堆顶的元素来更新最大连续子段和，便完成了s[x]从底往上的传递。

在查询时，我们只需要将 x所在链的链底—x 在线段树上对应的区间的最大连续子段和取出来即可。

这样一次修改的复杂度是$O(log^2n)$的，一次询问的复杂度是$O(\log n)$的。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=200010;

typedef long long ll;

int n,m,cnt;

int to[maxn<<1],next[maxn<<1],head[maxn],p[maxn],q[maxn],siz[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],sson[maxn];

ll v[maxn],f[maxn],g[maxn],ms[maxn];

char str[5];

struct heap

{

	priority_queue<ll> p1,p2;

	inline void push(ll x) {p1.push(x);}

	inline void erase(ll x) {p2.push(x);}

	inline ll top()

	{

		while(!p2.empty()&&p1.top()==p2.top())	p1.pop(),p2.pop();

		if(p1.empty())	return 0;

		return p1.top();

	}

}mx[maxn];

struct sag

{

	ll sl,sr,sm,s;

	sag () {}

	sag operator + (const sag &a) const

	{

		sag b;

		b.s=s+a.s;

		b.sl=max(sl,s+a.sl);

		b.sr=max(a.sr,sr+a.s);

		b.sm=max(sr+a.sl,max(sm,a.sm));

		return b;

	}

}s[maxn<<2];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

void dfs1(int x)

{

	siz[x]=1;

	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa[x])

	{

		fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs1(to[i]),siz[x]+=siz[to[i]];

		if(siz[to[i]]>siz[son[x]])	son[x]=to[i];

	}

}

void dfs2(int x,int tp)

{

	top[x]=tp,p[x]=++q[0],q[q[0]]=x;

	if(son[x])	dfs2(son[x],tp),sson[x]=sson[son[x]],ms[x]=ms[son[x]];

	else	sson[x]=x;

	g[x]=v[x];

	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa[x]&&to[i]!=son[x])

		dfs2(to[i],to[i]),g[x]+=f[to[i]],mx[x].push(ms[to[i]]);

	f[x]=max(0ll,g[x]+f[son[x]]),ms[x]=max(ms[x],f[x]),ms[x]=max(ms[x],mx[x].top());

}

void build(int l,int r,int x)

{

	if(l==r)

	{

		s[x].s=g[q[l]];

		s[x].sl=s[x].sr=max(g[q[l]],0ll);

		s[x].sm=max(g[q[l]],mx[q[l]].top());

		return ;

	}

	int mid=(l+r)>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	s[x]=s[lson]+s[rson];

}

void updata(int l,int r,int x,int a)

{

	if(l==r)

	{

		s[x].s=g[q[l]];

		s[x].sl=s[x].sr=max(g[q[l]],0ll);

		s[x].sm=max(g[q[l]],mx[q[l]].top());

		return ;

	}

	int mid=(l+r)>>1;

	if(a<=mid)	updata(l,mid,lson,a);

	else	updata(mid+1,r,rson,a);

	s[x]=s[lson]+s[rson];

}

sag query(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)	return s[x];

	int mid=(l+r)>>1;

	if(b<=mid)	return query(l,mid,lson,a,b);

	if(a>mid)	return query(mid+1,r,rson,a,b);

	return query(l,mid,lson,a,b)+query(mid+1,r,rson,a,b);

}

inline void modify(int x,ll y)

{

	sag t1,t2,t3;

	int flag=0;

	while(x)

	{

		t3=query(1,n,1,p[top[x]],p[sson[top[x]]]);

		if(flag)	mx[x].erase(t1.sm),mx[x].push(t2.sm);

		t1=t3;

		flag=1;

		g[x]+=y,updata(1,n,1,p[x]);

		t2=query(1,n,1,p[top[x]],p[sson[top[x]]]);

		y=t2.sl-f[top[x]],f[top[x]]=t2.sl;

		x=fa[top[x]];

	}

}

inline void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

int main()

{

	//freopen("A.in","r",stdin);

	//freopen("A.out","w",stdout);

	n=rd(),m=rd();

	int i,a,b;

	memset(head,-1,sizeof(head));

	for(i=1;i<=n;i++)	v[i]=rd();

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	dep[1]=1,dfs1(1),dfs2(1,1);

	build(1,n,1);

	for(i=1;i<=m;i++)

	{

		scanf("%s",str);

		if(str[0]=='M')

		{

			a=rd(),b=rd();

			modify(a,b-v[a]),v[a]=b;

		}

		else

		{

			a=rd();

			printf("%lld\n",query(1,n,1,p[a],p[sson[a]]).sm);

		}

	}

	return 0;

}//5 3 1 2 -3 -4 5 1 2 2 3 3 4 4 5 Q 2 C 4 1 Q 2

巴特西

【BZOJ5210】最大连通子块和树剖线段树+动态DP

【BZOJ5210】最大连通子块和

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

【BZOJ5210】最大连通子块和 树剖线段树+动态DP

【BZOJ5210】最大连通子块和

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

【BZOJ5210】最大连通子块和树剖线段树+动态DP