题意：支持单点修改，维护子树里的最大连通子块和。

---

思路：

扯皮：

$bzoj$卡常差评。

网上的题解大多用了跟什么最大子段和一样的转移方法。

但是我们实际上是可以用矩阵转移的传统$ddp$写法来做这道题的。

由于我推出来矩阵是$3\ast 3$的因此常数巨大$gg$了，因此蒟蒻博主只能提供思路和一份$TLE$的代码。

正题：

一道考虑链分治+$dp$套路题。

同样先考虑静态的版本。

显然可以fi,0/1f_{i,0/1}fi,0/1​表示以$i$为根的子树,$i$在/不在最大子块里是的最大子块和是多少。

然后显然有如下两个转移式：

fp,0=maxv∈son{fv,0,fv,1}f_{p,0}=max_{v\in son}\{f_{v,0},f_{v,1}\}fp,0​=maxv∈son​{

fv,0​,fv,1​}

fp,1=vali+∑v∈sonmax{fv,1,0}f_{p,1}=val_i+\sum_{v\in son}max\{f_{v,1},0\}fp,1​=vali​+∑v∈son​max{

fv,1​,0}。

现在考虑链分治，我们记一个gi,0/1g_{i,0/1}gi,0/1​表示跟以$i$为根的子树去掉$i$的重儿子所在子树之后,$i$在/不在最大子块里时的最大子块和是多少。

考虑推$g$:

gp,0=maxv∈son,v̸=hson{fv,0,fv,1}g_{p,0}=max_{v\in son,v\not=hson}\{f_{v,0},f_{v,1}\}gp,0​=maxv∈son,v̸​=hson​{

fv,0​,fv,1​}

gp,1=fi,1=vali+∑v∈son,v̸=hsonmax{0,fv,1}g_{p,1}=f_{i,1}=val_i+\sum_{v\in son,v\not=hson}max\{0,f_{v,1}\}gp,1​=fi,1​=vali​+∑v∈son,v̸​=hson​max{

0,fv,1​}

于是就可以用fhsonf_{hson}fhson​和gpg_pgp​来更新fpf_pfp​：

fp,0=max{gp,0,fhson,0,fhson,1}f_{p,0}=max\{g_{p,0},f_{hson,0},f_{hson,1}\}fp,0​=max{

gp,0​,fhson,0​,fhson,1​}

fp,1=gp,1+valp+max{0,fhson,1}f_{p,1}=g_{p,1}+val_p+max\{0,f_{hson,1}\}fp,1​=gp,1​+valp​+max{

0,fhson,1​}

那么这个可以用矩阵的形式来表示：

(0fp,0fp,1)=(0−∞−∞gp,000gp,1+valp−∞gp,1+valp)∗(0fhson,0fhson,1) \left ( \begin{matrix} 0\\ f_{p,0}\\ f_{p,1}\\ \end{matrix} \right)= \left ( \begin{matrix} 0&-\infin&-\infin\\ g_{p,0}&0&0\\ g_{p,1}+val_p&-\infin&g_{p,1}+val_p\\ \end{matrix} \right)* \left( \begin{matrix} 0\\ f_{hson,0}\\ f_{hson,1}\\ \end{matrix} \right) ⎝⎛​0fp,0​fp,1​​⎠⎞​=⎝⎛​0gp,0​gp,1​+valp​​−∞0−∞​−∞0gp,1​+valp​​⎠⎞​∗⎝⎛​0fhson,0​fhson,1​​⎠⎞​

于是对于每条重链开一棵线段树来维护左边$3\ast 3$矩阵的转移即可。

代码（被卡常）：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;typedef long long ll;typedef pair
     
       pii;const int N=2e5+5;const ll inf=1e15;inline int read(){
    	int ans=0,w=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')w=-1;ch=getchar();}	while(isdigit(ch))ans=(((ans<<2)+ans)<<1)+(ch^48),ch=getchar();	return ~w?ans:-ans;}struct deletable_queue{
    	priority_queue
      
       a,b;	inline void push(const ll&x){
    a.push(x);}	inline void del(const ll&x){
    b.push(x);}	inline ll top(){
    while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.top();}}S[N];int fa[N],top[N],num[N],hson[N],siz[N],dep[N],pred[N],vl[N],bot[N],n,m,tot=0;ll f[N][2],g[N][2];vector
       
        e[N];inline ll M(const ll&a,const ll&b){
    return (a!=-inf)&&(b!=-inf)?a+b:-inf;}void dfs1(int p){
    	siz[p]=1;	for(ri i=0,v;i
        
         siz[hson[p]])hson[p]=v;	}}void dfs2(int p,int tp){
    	top[p]=tp,pred[num[p]=++tot]=p,bot[tp]=p;	g[p][0]=g[p][1]=f[p][0]=0,f[p][1]=vl[p];	if(!hson[p])return;	dfs2(hson[p],tp);	for(ri i=0,v;i
         
          >1) struct Node{ int l,r,v; ll f[2],g[2]; Mat trans; inline void init(){ trans[0][0]=0,trans[0][1]=-inf,trans[0][2]=-inf; trans[1][0]=g[0],trans[1][1]=0,trans[1][2]=0; trans[2][0]=g[1]+v,trans[2][1]=-inf,trans[2][2]=g[1]+v; } inline pii val(){ return pii(f[0],f[1]);} }T[N<<2]; inline void Set(int p){ int k=pred[T[p].l]; T[p].f[0]=f[k][0],T[p].f[1]=f[k][1]; T[p].g[0]=g[k][0],T[p].g[1]=g[k][1]; T[p].v=vl[k],T[p].init(); } inline void pushup(int p){ T[p].trans=T[lc].trans*T[rc].trans;} inline void build(int p,int l,int r){ T[p].l=l,T[p].r=r; if(l==r)return Set(p); build(lc,l,mid),build(rc,mid+1,r),pushup(p); } inline void update(int p,int k){ if(T[p].l==T[p].r)return Set(p); update(k<=mid?lc:rc,k),pushup(p); } inline Mat query(int p,int ql,int qr){ if(ql<=T[p].l&&T[p].r<=qr)return T[p].trans; if(qr<=mid)return query(lc,ql,qr); if(ql>mid)return query(rc,ql,qr); return query(lc,ql,mid)*query(rc,mid+1,qr); } inline pii query(int p,int k){ if(T[p].l==T[p].r)return T[p].val(); return query(k<=mid?lc:rc,k); }}inline pii ask(int p){ int bt=bot[top[p]]; if(p==bt)return SGT::query(1,num[p]); Mat upd=SGT::query(1,num[p],num[bt]-1); pii val=SGT::query(1,num[bt]),ret; ret.fi=max(M(upd[1][0],0ll),max(M(upd[1][1],val.fi),M(upd[1][2],val.se))); ret.se=max(M(upd[2][0],0ll),max(M(upd[2][1],val.fi),M(upd[2][2],val.se))); return ret;}inline void update(int p,int x){ vl[p]=x,f[p][1]=g[p][1]+vl[p]+max(0ll,f[hson[p]][1]); while(1){ int ft=fa[top[p]],tp=top[p]; if(ft){ pii upd=ask(tp); S[ft].del(max(upd.fi,upd.se)); g[ft][1]-=max(0ll,upd.se); } SGT::update(1,num[p]); if(ft){ pii upd=ask(tp); p=ft; S[p].push(max(upd.fi,upd.se)); g[p][1]+=max(0ll,upd.se); g[p][0]=S[p].top(); f[p][0]=max(g[p][0],max(f[hson[p]][0],f[hson[p]][1])); f[p][1]=vl[p]+g[p][1]+max(0ll,f[hson[p]][1]); } else break; }}char s[2];int main(){ n=read(),m=read(); for(ri i=1;i<=n;++i)vl[i]=read(),S[i].push(0ll); for(ri i=1,u,v;i