题目：https://www.lydsy.com/JudgeOnline/problem.php?id=5210
似乎像bzoj4712一样，依然可以用别的方法做。但还是只写了动态DP。
当然是dp[ ][0/1]表示选/不选自己这个点的最大值。
本来想生硬地弄一个矩阵，但发现时间可能不太好，因为是3×3的矩阵，有27倍的时间。
用g[ ][0/1]表示dp的除去重儿子的意义。那么dp[ ][1]就是自己的g[ ][1]加上重链里的靠近自己的一段g[ ][1]，线段树上表现为g[1]的最大前缀；dp[ ][0]就是自己的g[ ][0]与重儿子的g[ ][0]取max，线段树上表现为重链的g[1]的最大子段和。所以对于线段树的g[0]其实不用真的开出来，算答案的时候弄一弄g[1]就行了；把“轻儿子的dp[0/1]最大值”记录在自己的点上，不用放到线段树上。
接下来用g表示g[1]。
发现修改很难弄。因为最大前缀 fl 是可以弄成>=0的，所以g+=max( 0 , fl )可以看作 g += fl ；这样修改了 fl 之后就能直接 g += fl(新) - fl(旧)了；但那个“轻儿子的dp[0/1]最大值”怎么应对修改？
于是看了一眼。原来可以用可删堆呀！也不知道自己写的是不是可删堆，反正可以开一个“删除堆”，要删的东西加进去；用堆里元素的时候看看堆顶和“删除堆”的堆顶是否一样，如果一样就说明该元素已删除，在两个堆里都把堆顶删了。
然后WA了。发现自己写错了。那个 "最大子段和sm"还有 fl 是重链上不包括自己的，给写成包括自己了。不过现在觉得是不是就算写成包括自己也可以？
改的时候注意因为在 calc 里要用到 g ，所以算 原来的值 k0 之前不能已经把 g 给改了。
然后WA了。对拍半天，发现dp[ ][0]合并的时候不是重链上g的最大子段和！因为可能存在于重链上某个点的轻儿子里！
不过这样也简单，只要把“轻儿子的dp[0/1]最大值”，也就是那个堆顶，也放在线段树上，取一个区间max就行了。
注意这样就要算完 k0 之后再改自己的堆！
然后就能以一个较慢不过好像还算正常的速度A了。
然后发现线段树上查询时写成包括自己的也行。不如说更好，这样就不用管更新自己是在算k0前还是算k0后了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ls Ls[cr] #define rs Rs[cr] #define ll long long using namespace std; const int N=2e5+5,M=N<<1; int n,m,w[N],hd[N],xnt,to[M],nxt[M]; int tot,dfn[N],rnk[N],top[N],fa[N],son[N],siz[N],bj[N],Ls[M],Rs[M]; ll dp[N][2],g[N]; ll Mx(ll a,ll b){return a>b?a:b;} struct Node{ ll fl,fr,sm,vl,mx; Node(){fl=fr=sm=vl=mx=0;} Node operator+ (const Node &b)const { Node c; c.fl=Mx(fl,vl+b.fl); c.fr=Mx(b.fr,b.vl+fr); c.vl=vl+b.vl; c.sm=Mx(sm,b.sm); c.sm=Mx(c.sm,Mx(c.fl,c.fr)); c.sm=Mx(c.sm,fr+b.fl); c.mx=Mx(mx,b.mx); return c; } }t[M],I; priority_queue<ll> q[N],qd[N]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} void dfs(int cr) { siz[cr]=1; dp[cr][1]=w[cr]; dp[cr][0]=0; for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa[cr]) { fa[v]=cr; dfs(v); siz[cr]+=siz[v]; siz[v]>siz[son[cr]]?son[cr]=v:0; dp[cr][1]+=Mx(0,dp[v][1]); dp[cr][0]=Mx(dp[cr][0],Mx(dp[v][0],dp[v][1])); } } void dfsx(int cr) { dfn[cr]=++tot; rnk[tot]=cr; g[cr]=w[cr]; q[cr].push(0); if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr]); else {bj[top[cr]]=dfn[cr]; return;} for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa[cr]&&v!=son[cr]) { top[v]=v; dfsx(v); g[cr]+=Mx(0,dp[v][1]); q[cr].push(Mx(dp[v][0],dp[v][1])); } } ll fnd(int cr) { while(qd[cr].size()&&q[cr].top()==qd[cr].top()) q[cr].pop(),qd[cr].pop(); return q[cr].top(); } void build(int l,int r,int cr) { if(l==r) { t[cr].fl=t[cr].fr=t[cr].sm=Mx(0,g[rnk[l]]); t[cr].vl=g[rnk[l]];t[cr].mx=fnd(rnk[l]); return; } int mid=l+r>>1; ls=++tot; build(l,mid,ls); rs=++tot; build(mid+1,r,rs); t[cr]=t[ls]+t[rs]; } void updt(int l,int r,int cr,int p) { if(l==r) { t[cr].fl=t[cr].fr=t[cr].sm=Mx(0,g[rnk[l]]); t[cr].vl=g[rnk[l]];t[cr].mx=fnd(rnk[l]); return; } int mid=l+r>>1; if(p<=mid)updt(l,mid,ls,p); else updt(mid+1,r,rs,p); t[cr]=t[ls]+t[rs]; } Node query(int l,int r,int cr,int L,int R) { if(L>R)return I; if(l>=L&&r<=R)return t[cr]; int mid=l+r>>1; if(R<=mid)return query(l,mid,ls,L,R); if(mid<L) return query(mid+1,r,rs,L,R); return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R); } Node calc(int cr) { Node ret=query(1,n,1,dfn[cr],bj[top[cr]]);//bj[top[cr]]//dfn[cr]+1 ret.sm=Mx(ret.sm,ret.mx); return ret; } void cz(int x,int y) { g[x]+=y-w[x]; w[x]=y;//for calc is related to g[](x=top[x]) Node k0=calc(top[x]); updt(1,n,1,dfn[x]); Node k1=calc(top[x]);//updt is related to g[]! while(fa[top[x]]) { x=fa[top[x]]; g[x]+=k1.fl-k0.fl;//fl>=0 qd[x].push(Mx(k0.fl,k0.sm)); q[x].push(Mx(k1.fl,k1.sm)); k0=calc(top[x]); updt(1,n,1,dfn[x]); k1=calc(top[x]);//updt!not be in front or the last updt will be missed } } int main() { n=rdn(); m=rdn(); for(int i=1;i<=n;i++)w[i]=rdn(); for(int i=1,u,v;i<n;i++) { u=rdn(); v=rdn(); add(u,v); add(v,u); } dfs(1); top[1]=1; dfsx(1); tot=1; build(1,n,1); char ch[5]; for(int i=1,x,y;i<=m;i++) { scanf("%s",ch); if(ch[0]=='M') { x=rdn(); y=rdn(); cz(x,y); } else { x=rdn(); Node d=calc(x); printf("%lld\n",Mx(d.fl,d.sm)); } } return 0; }