【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
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
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