本文共 8470 字，大约阅读时间需要 28 分钟。
口胡的弱智型题解：
$f_x$表示$x$的子树中，与$x$联通（或为空集）的最大联通子块和。
$ans_x$表示$x$的子树中，最大联通子块和。
$y\ is\ son\ of\ x$
$f_x=max(0,\sum f_y+v_x)$
$ans_x=max(f_x,ans_y)$
不带修改的话一次树dp即可。
带修改的，考虑用树剖维护，
设$g_x=v_x+\sum_{y|y是x的轻儿子}f_y$，$son_x$表示$x$的重儿子
$f_x=max(0,g_x+f_{son_x})$
试着看一条重链，链底的$f_x=g_x=max(0,v_x)$,往上$f_x=max(0,g_x+f_{son_x})$。这就是一个以x开头的最大连续子段和，可以用线段树维护！
也就是说，在线段树上存下每个x的g就可以查到每个x对应的f了。而修改的时候，重链上线段树上修改g，再跳到上一条重链继续修改即可。（第一次修改g是因为v的改变，往上跳修改是因为$f_{轻儿子}$的改变）
再考虑ans的维护。如果用$s_x$表示轻儿子的$ans$的最大值
$ans_x=max(s_x,s_{son_x},f_x)$
$s_x$和$g_x$的差别在于取最大值在修改时不好处理，所以$s_x$不能是一个值(轻儿子的$ans$的最大值)而是一个set(存所有轻儿子的$ans$值)，这样s和g的修改就一样操作了。
然后这个$s_x$可以直接放在线段树上，x的节点上，这样很容易取最大值。
1 //Achen 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define Formylove return 0 13 #define For(i,a,b) for(int i=(a);i<=(b);i++) 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 15 const int N=400007; 16 typedef long long LL; 17 typedef double db; 18 using namespace std; 19 int n,m; 20 LL v[N]; 21 char op[5]; 22 23 template void read(T &x) { 24 char ch=getchar(); x=0; T f=1; 25 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 26 if(ch=='-') f=-1,ch=getchar(); 27 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 28 } 29 30 struct sg { 31 LL sum,sl,sr,sm; 32 friend sg operator +(const sg&ls,const sg&rs) { 33 sg a; 34 a.sum=ls.sum+rs.sum; 35 a.sl=max(ls.sl,ls.sum+rs.sl); 36 a.sr=max(rs.sr,rs.sum+ls.sr); 37 a.sm=max(max(ls.sm,rs.sm),ls.sr+rs.sl); 38 return a; 39 } 40 }tr[N<<2]; 41 multiset s[N]; 42 43 #define lc x<<1 44 #define rc ((x<<1)|1) 45 #define mid ((l+r)>>1) 46 sg qry(int x,int l,int r,int ql,int qr) { 47 if(l>=ql&&r<=qr) return tr[x]; 48 if(qr<=mid) return qry(lc,l,mid,ql,qr); 49 if(ql>mid) return qry(rc,mid+1,r,ql,qr); 50 return qry(lc,l,mid,ql,qr)+qry(rc,mid+1,r,ql,qr); 51 } 52 53 void update(int x,int l,int r,int pos,LL g,LL mg) { 54 if(l==r) { 55 tr[x].sum=g; 56 tr[x].sl=tr[x].sr=max(0LL,g); 57 tr[x].sm=max(mg,g); 58 return ; 59 } 60 if(pos<=mid) update(lc,l,mid,pos,g,mg); 61 else update(rc,mid+1,r,pos,g,mg); 62 tr[x]=tr[lc]+tr[rc]; 63 } 64 65 int ecnt,fir[N],nxt[N<<1],to[N<<1]; 66 void add(int u,int v) { 67 nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; 68 nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; 69 } 70 71 int R[N],fa[N],sz[N]; 72 void dfs(int x,int Fa) { 73 sz[x]=1; 74 fa[x]=Fa; 75 R[x]=R[Fa]+1; 76 for(int i=fir[x];i;i=nxt[i]) if(to[i]!=Fa) { 77 dfs(to[i],x); 78 sz[x]+=sz[to[i]]; 79 } 80 } 81 82 int top[N],ed[N],dfk,tid[N],tot; 83 LL ftf[N],stf[N]; 84 void DFS(int x,int Top) { 85 tid[x]=++tot; 86 top[x]=Top; 87 ed[Top]=x; 88 int mson=0; 89 for(int i=fir[x];i;i=nxt[i]) 90 if(to[i]!=fa[x]&&(!mson||sz[to[i]]>sz[mson])) 91 mson=to[i]; 92 if(!mson) { 93 update(1,1,n,tid[x],v[x],0); 94 return; 95 } 96 DFS(mson,Top); 97 LL gx=v[x],mg=0; 98 for(int i=fir[x];i;i=nxt[i]) 99 if(to[i]!=fa[x]&&to[i]!=mson) {100 DFS(to[i],to[i]);101 sg tp=qry(1,1,n,tid[to[i]],tid[ed[top[to[i]]]]);102 gx+=tp.sl; 103 mg=max(mg,tp.sm);104 s[x].insert(tp.sm);105 ftf[to[i]]=tp.sl;106 stf[to[i]]=tp.sm;107 }108 update(1,1,n,tid[x],gx,mg);109 }110 111 void change(int x,LL y) {112 sg tp=qry(1,1,n,tid[x],tid[x]),tpz;113 LL gx=tp.sum-v[x]+y; v[x]=y;114 LL mg=0; if(!s[x].empty()) mg=*s[x].rbegin();115 update(1,1,n,tid[x],gx,mg);116 for(;;) {117 int z=fa[top[x]];118 if(!z) break;119 tp=qry(1,1,n,tid[top[x]],tid[ed[top[x]]]);120 tpz=qry(1,1,n,tid[z],tid[z]);121 LL gx=tpz.sum-ftf[top[x]]+tp.sl;122 s[z].erase(s[z].find(stf[top[x]]));123 s[z].insert(tp.sm); 124 ftf[top[x]]=tp.sl;125 stf[top[x]]=tp.sm;126 LL mg=*s[z].rbegin();127 update(1,1,n,tid[z],gx,mg);128 x=z;129 }130 }131 132 int main() {133 #ifdef ANS134 freopen(".in","r",stdin);135 freopen(".out","w",stdout);136 #endif137 read(n); read(m);138 For(i,1,n) read(v[i]);139 For(i,2,n) {140 int u,v;141 read(u); read(v);142 add(u,v);143 }144 dfs(1,0);145 DFS(1,1);146 For(ti,1,m) {147 scanf("%s",op);148 int x; LL y;149 if(op[0]=='M') {150 read(x); read(y);151 change(x,y);152 }153 else {154 read(x);155 sg tp=qry(1,1,n,tid[x],tid[ed[top[x]]]);156 LL ans=tp.sm;157 printf("%lld\n",ans);158 }159 }160 Formylove;161 }
本来想写题解，但是代码里面注释得已经非常详细了，就放一个别人的吧
这种修改操作只有权值加的好像很套路呀。
1 //Achen 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define Formylove return 0 13 #define For(i,a,b) for(int i=(a);i<=(b);i++) 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 15 const int N=400007; 16 typedef long long LL; 17 typedef double db; 18 using namespace std; 19 int n,m; 20 char op[5]; 21 22 template void read(T &x) { 23 char ch=getchar(); x=0; T f=1; 24 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 25 if(ch=='-') f=-1,ch=getchar(); 26 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 27 } 28 29 LL v[N],sg[N<<2],lz[N<<2]; 30 #define lc x<<1 31 #define rc ((x<<1)|1) 32 #define mid ((l+r)>>1) 33 void down(int x,int l_len,int r_len) { 34 if(!lz[x]) return; 35 sg[lc]+=lz[x]; lz[lc]+=lz[x]; 36 sg[rc]+=lz[x]; lz[rc]+=lz[x]; 37 lz[x]=0; 38 } 39 40 LL qry(int x,int l,int r,int ql,int qr) { 41 if(l>=ql&&r<=qr) return sg[x]; 42 down(x,mid-l+1,r-mid); 43 if(qr<=mid) return qry(lc,l,mid,ql,qr); 44 if(ql>mid) return qry(rc,mid+1,r,ql,qr); 45 return min(qry(lc,l,mid,ql,qr),qry(rc,mid+1,r,ql,qr)); 46 } 47 48 int lef[N]; 49 void update(int x,int l,int r,int ql,int qr,LL v) { 50 if(l>=ql&&r<=qr) { 51 if(l==r&&lef[l]) return; 52 sg[x]+=v; if(l!=r) lz[x]+=v; return; 53 } 54 down(x,mid-l+1,r-mid); 55 if(ql<=mid) update(lc,l,mid,ql,qr,v); 56 if(qr>mid) update(rc,mid+1,r,ql,qr,v); 57 sg[x]=min(sg[lc],sg[rc]); 58 } 59 60 int ecnt,fir[N],nxt[N<<1],to[N<<1]; 61 void add(int u,int v) { 62 nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; 63 nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; 64 } 65 66 int fa[N],sz[N]; 67 void dfs(int x,int Fa) { 68 sz[x]=1; 69 fa[x]=Fa; 70 for(int i=fir[x];i;i=nxt[i]) if(to[i]!=Fa) { 71 dfs(to[i],x); 72 sz[x]+=sz[to[i]]; 73 } 74 } 75 76 int top[N],tid[N],ftid[N],tot; 77 void DFS(int x,int Top) { 78 tid[x]=++tot; 79 ftid[tot]=x; 80 top[x]=Top; 81 int mson=0; 82 for(int i=fir[x];i;i=nxt[i]) 83 if(to[i]!=fa[x]&&(!mson||sz[to[i]]>sz[mson])) 84 mson=to[i]; 85 if(!mson) { 86 lef[tid[x]]=1; 87 update(1,1,n,tid[x],tid[x],0); //设叶子 v[x]==g[x] 88 return; 89 } 90 LL gx=0; 91 DFS(mson,Top); 92 LL tp=qry(1,1,n,tid[mson],tid[mson]); 93 gx+=min(v[mson],v[mson]-tp); 94 for(int i=fir[x];i;i=nxt[i]) 95 if(to[i]!=fa[x]&&to[i]!=mson) { 96 DFS(to[i],to[i]); 97 LL tp=qry(1,1,n,tid[to[i]],tid[to[i]]); 98 gx+=min(v[to[i]],v[to[i]]-tp); 99 }100 update(1,1,n,tid[x],tid[x],v[x]-gx);101 }102 103 void change(int x,LL y) {104 //v[x]增加了y 105 LL tp=qry(1,1,n,tid[x],tid[x]);106 LL gx=lef[tid[x]]?v[x]+y:v[x]-tp;//如果是叶子，g始终等于v!!!! 107 update(1,1,n,tid[x],tid[x],y); //v-g增加y 108 if(gx<=v[x]) { //原来选g,现在仍选g 109 v[x]+=y; return;110 }111 LL plus;112 if(v[x]+y<=gx) plus=y; //原来选v,现在选仍v，f增加y 113 else plus=gx-v[x]; //原来选v,现在选g,f增加g-v 114 v[x]+=y;115 for(;;) {116 //f[x]增加了plus，即g[z]增加了plus 117 int z=fa[x];118 if(!z) break;119 tp=qry(1,1,n,tid[z],tid[z]);120 LL gz=v[z]-tp;121 update(1,1,n,tid[z],tid[z],-plus);122 if(gz>=v[z]) return; //原来选v->g↑,仍选v 123 if(v[z]<=gz+plus) plus=v[z]-gz,x=z; //原来选g->现在选v(由g->v最多n+m次，故可以暴力)124 else { //原来选g->现在g↑仍选g 125 int t=top[z];126 int l=tid[t],r=tid[z],rs=r;127 while(l<=r) {128 tp=qry(1,1,n,mid,tid[z]);129 if(tp>=plus) rs=mid,r=mid-1;130 else l=mid+1;131 }132 if(tid[z]>rs) update(1,1,n,rs,tid[z]-1,-plus);133 x=ftid[rs];134 }135 }136 }137 138 int main() {139 #ifdef ANS140 freopen(".in","r",stdin);141 freopen(".out","w",stdout);142 #endif143 read(n); 144 For(i,1,n) read(v[i]);145 For(i,2,n) {146 int u,v;147 read(u); read(v);148 add(u,v);149 }150 dfs(1,0);151 DFS(1,1);152 read(m);153 For(ti,1,m) {154 scanf("%s",op);155 int x; LL y;156 if(op[0]=='C') {157 read(x); read(y);158 change(x,y);159 }160 else {161 read(x);162 LL ans=qry(1,1,n,tid[x],tid[x]);163 ans=min(v[x],v[x]-ans);164 printf("%lld\n",ans);165 }166 }167 Formylove;168 }169 /*170 4171 4 3 2 1172 1 2173 1 3174 4 2175 4176 C 4 10177 Q 1178 */
转载于:https://www.cnblogs.com/Achenchen/p/9525688.html
