国际惯例的题面:
这题......最大连通子块和显然可以DP，加上修改显然就是动态DP了......考虑正常情况下怎么DP:我们令a[i]表示选择i及i的子树中的一些点，最大连通子块和;b[i]表示在i的子树中选择一些点(不一定包含i)，最大连通子块和。那么我们要询问i的子树的话，答案就是b[i]了。考虑这个DP怎么转移，a[i]=max(sigma(j:SON_i)a[j]+v[i],0),b[i]=max((j:SON_i)b[j],a[i])。陈俊锟说过，树上动态DP，就是把树拆成链，分离轻重儿子的转移。于是我们重新定义DP:f[i]表示从i所在的重链到i，选择连续一段和连续一段的子树，最大连通子块和(可以不包含i选择空段，类似a[i]);g[i]表示计算i这个点本身和i的虚孩子们，形成的最大连续子块和。dp[i]表示从i所在的重链到i，选择连续一段和连续一段的子树，或者从某个点的虚孩子中选择一个连通块，最大连通子块和(显然这个不一定包含i)。这样的话，我们的转移就有:g[i]=v[i]+sigma(j:LIGHTSON_i)f[j],f[i]=max(g[i]+f[HEAVYSON_i],0),dp[pos]=max(f[i],dp[HEAVYSON_i],max((j:LIGHTSON_i)dp[j]))。这个转移初始化的话直接线性DP一遍就好了。考虑怎么动态，这里的轻重孩子的转移都定义好了，我们只需要修改一些点的g和dp值，给他的父亲所在的重链当做输入值就好。考虑怎么查询，如果是一条链的话，我们查询的就是最大子段和。树上的话，我们对于重链，也能查询g的最大子段和。对于最优解不在这条链上的情况，我们用这个点的所有轻儿子的dp值去更新它单点的最大连续子段和就好，显然这是正确的。也就是说，我们还需要维护一下DP值。考虑DP值是取max，所以用multiset去维护一下就好。(其实这题我本来想写类似矩阵乘法的DP转移的，然后发现不会查询，于是只好分析题目性质列DP了)代码: 
1 #include2 #include 3 #include 4 using std::max; 5 typedef long long int lli; 6 const int maxn=2e5+1e2; 7 8 lli in[maxn],f[maxn],g[maxn],idp[maxn]; // f means from chain to top , g means cost of pos and virtualsons of pos , idp means max segment sum . 9 int s[maxn],t[maxn<<1],nxt[maxn<<1];10 int dep[maxn],siz[maxn],fa[maxn],son[maxn],top[maxn],id[maxn],rec[maxn],mxd[maxn];11 std::multiset ls[maxn];12 13 struct SegmentTree {14 int l[maxn<<2],r[maxn<<2],lson[maxn<<2],rson[maxn<<2],cnt;15 SegmentTree() { cnt = 1 ; }16 struct Node {17 lli sl,sr,su,mx;18 friend Node operator + (const Node &a,const Node &b) {19 return (Node){max(a.sl,a.su+b.sl),max(a.sr+b.su,b.sr),a.su+b.su,max(a.sr+b.sl,max(a.mx,b.mx))};20 }21 inline void fil(int id) {22 sl = sr = max( g[rec[id]] , 0ll ) , su = g[rec[id]] , mx = max( g[rec[id]] , *ls[rec[id]].rbegin() );23 }24 }ns[maxn<<2];25 inline void build(int pos,int ll,int rr) {26 l[pos] = ll , r[pos] = rr;27 if( ll == rr ) return ns[pos].fil(ll);28 const int mid = ( ll + rr ) >> 1;29 build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+1,rr) ,30 ns[pos] = ns[lson[pos]] + ns[rson[pos]];31 }32 inline void update(int pos,const int &tar) {33 if( l[pos] == r[pos] ) return ns[pos].fil(tar);34 const int mid = ( l[pos] + r[pos] ) >> 1;35 tar <= mid ? update(lson[pos],tar) : update(rson[pos],tar);36 ns[pos] = ns[lson[pos]] + ns[rson[pos]];37 }38 inline Node query(int pos,const int &ll,const int &rr) {39 if( ll <= l[pos] && r[pos] <= rr ) return ns[pos];40 const int mid = ( l[pos] + r[pos] ) >> 1;41 if( rr <= mid ) return query(lson[pos],ll,rr);42 else if( ll > mid ) return query(rson[pos],ll,rr);43 else return query(lson[pos],ll,rr) + query(rson[pos],ll,rr);44 }45 }sgt;46 typedef SegmentTree::Node Node;47 48 inline void addedge(int from,int to) {49 static int cnt = 0;50 t[++cnt] = to , nxt[cnt] = s[from] , s[from] = cnt;51 }52 inline void pr(int pos) {53 siz[pos] = 1;54 for(int at=s[pos];at;at=nxt[at]) if( t[at] != fa[pos] ) {55 fa[t[at]] = pos , dep[t[at]] = dep[pos] + 1 , pr(t[at]) , siz[pos] += siz[t[at]];56 if( siz[t[at]] > siz[son[pos]] ) son[pos] = t[at];57 }58 }59 inline void pre(int pos) {60 static int iid;61 top[pos] = pos == son[fa[pos]] ? top[fa[pos]] : pos , rec[id[pos]=++iid] = pos , mxd[top[pos]] = iid , g[pos] = in[pos];62 if( son[pos] ) pre(son[pos]) , idp[pos] = idp[son[pos]] , f[pos] = f[son[pos]];63 for(int at=s[pos];at;at=nxt[at]) if( t[at] != fa[pos] && t[at] != son[pos] ) pre(t[at]) , g[pos] += f[t[at]] , ls[pos].insert(idp[t[at]]);64 f[pos] = max( f[pos] + g[pos] , 0ll ) , idp[pos] = max( idp[pos] , max( f[pos] , *ls[pos].rbegin() ) );65 }66 67 inline Node query(int pos) {68 return sgt.query(1,id[pos],mxd[top[pos]]);69 }70 inline void update(int pos,int nv) {71 Node od,nw;72 int fst = 1;73 od.sl = in[pos] , nw.sl = nv , in[pos] = nv;74 while(pos) {75 g[pos] += nw.sl - od.sl;76 if( !fst ) ls[pos].erase(ls[pos].find(od.mx)) , ls[pos].insert(nw.mx);77 od = sgt.query(1,id[top[pos]],mxd[top[pos]]) , sgt.update(1,id[pos]) , nw = sgt.query(1,id[top[pos]],mxd[top[pos]]);78 fst = 0 , pos = fa[top[pos]];79 }80 }81 82 int main() {83 static int n,m;84 static char o[10];85 scanf("%d%d",&n,&m);86 for(int i=1;i<=n;i++) scanf("%lld",in+i) , ls[i].insert(0);87 for(int i=1,a,b;i