题解 P4643 【【模板】动态dp】

在上古论文中发现了一种神奇的做法…… $O(nlogn)$把树剖吊起来打…… 于是轻松拿到了本题的rk1(但是这份代码封装还是很多的，应该还有很多卡常空间) _____________________ ## 本题题解 ### 什么是动态dp 所谓动态dp就是一种黑科技允许你对于一个dp问题进行修改操作 先给你一个正常的dp问题，比如没有上司的舞会 然后我们要不停的修改参数此时问题的难度就由黄牌骤增至黑牌了 然后传统的做法是使用树链剖分(链分治) 我们先对整颗树做一个树剖，然后一条重链一条重链的进行dp 先来看普通的dp方程，设$Dp_{i,0}$为这个点不在独立时的最大收益，$Dp_{i,1}$为在的时候的最大收益 ## $Dp_{u,0}=\sum_{v \in u.son}max(Dp_{v,0},Dp_{v,1})$ ## $Dp_{u,1}=\sum_{v \in u.son}Dp_{v,0}$ 然后我们发现这个东西似乎可以变换一下顺序也没什么影响，所以我们一条重链一条重链的dp 换句话说我们采取一种dfs和bfs混合的方式遍历这颗树，每次到达一个重链的顶部的时候我们直接将这个重链全部塞到队列里，然后我们递归下去遍历和重链相连的所有重链，最后处理这个重链，当处理完这个重链之后我们发现我们已经处理完了这个重链顶所在的子树了 那么我们对于重链上的每一个点，先根据轻儿子的dp值(因为轻儿子一定是其他重链的顶部所以dp值必定已经计算好)，计算出一个$ldp_{i,0/1}$ ## $ldp_{u,0}=\sum_{v \in u.lightson}max(Dp_{v,0},Dp_{v,1})$ ## $ldp_{u,1}=\sum_{v \in u.lightson}Dp_{v,0}$ 此时我们根据这个ldp值在重链上跑一个序列的dp ## $Dp_{u,0}=ldp_{u,0}+max(Dp_{u.heavyson,0},Dp_{u.heavyson,1})$ ## $Dp_{u,1}=ldp_{u,1}+Dp_{u.heavyson,0}$ 此时你可能会说，这有什么用……还不是$O(n)$的dp而且还多了一堆常数 但是这意味着我们成功的将树上的问题转化为了序列问题，所以我们现在可以使用线段树维护重链上的dp值，从而可以支持快速修改 具体来讲，当我们修改一个点的值的时候，我们在对应的重链的线段树上进行修改，此时会改变重链顶部的dp值，然后会改变重链顶的father的ldp值，然后又对应了线段树上的单点修改，此时又会改变另一个重链顶的dp值， 这样反复几次，我们就可以在$O(log^2n)$时间内完成单点修改 问题来了怎么线段树上维护dp值啊 很简单，利用immortalICO神仙给出的黑科技，我们将转移写成Floyd矩乘的形式 我们将平常的矩阵乘法换成这样的形式 ## $C_{i,j}=\max_{k}(A_{i,k}+B_{k,j})$ 可以证明这个重定义之后的矩乘仍然具有结合律 单位矩阵是中间一行0剩余的地方全部是$- \infty$ 那么我们发现事实上重链上的转移可以写成这样的矩乘 $$\begin{bmatrix} dp_{i-1,0} \\ dp_{i-1,1} \end{bmatrix} × \begin{bmatrix} ldp_{i,0} & ldp_{i,0} \\ ldp_{i,1} & -\infty \end{bmatrix}$$ 然后我们就可以在线段树上愉快的维护矩阵连乘积啦，通过维护矩阵连乘积我们就可以实现$O(8log^2n)$的修改操作了 ~~愚蠢的$O(nlog^2n)$做法到此结束，我们开始讲解上古魔法~~ _______________ ### 上古科技：“全局平衡二叉树" 可以去翻07年的论文”QTREE 解法的一些研究"，~~(“全局平衡二叉树"这个中二的名字是论文里说的)~~ 众所周知把刚才的树剖换成lct就可以做到一个log了，但是我们发现lct实在是常数太!大!了！绝对是跑不过实现的优秀的一点的树剖的 但是我们对于lct的复杂度证明却很感兴趣，为啥同样是操作了logn个数据结构，把线段树换成常数更大的splay复杂度反而少了一个log呢？(刚才这句话严格来讲是病句，常数和复杂度没有任何关联) 具体证明需要用到势能分析，但是感性理解一下就是如果我们把lct上的虚边也看成splay的边的话，我们发现整棵lct变成了一棵大splay，只是有些点度数不是2了 但是这些点度不是2的点并未破坏splay的势能分析换句话说势能分析对整颗大splay仍然生效,所以你的$log$次splay在整个大splay上只是一次splay而已 复杂度自然是均摊$O(logn)$了 但是，我们发现这是颗静态树，使用splay实在是大(常)材(数)小(过)用(大)了 于是我们考虑将lct强行静态化，换句话说，建一个像splay一样的全局平衡的树 观察到线段树只是局部平衡的，在碰到专业卡链剖的数据--链式堆(根号n个长度为根号n的链连成完全二叉树的形状)的时候会导致算上虚边之后的整颗树左倾或者右倾 此时我们发现如果在建线段树的时候做点手脚，我们把线段树换成二叉查找树bst，并且这个bst不是严格平衡的话，我们可以做到更加优秀的复杂度，使得算上虚边之后的树树高达到$O(logn)$级别 我们还是在树上dfs，但是对于重链建bst的时候我们并不建一个完美的bst，而是将每一个节点附上一个权值，权值为它所有轻儿子的siz之和+1，然后我们每次找这个链的带权重心，把他作为这一级的父亲，然后递归两边进行建bst 当然我们发现最坏情况下我们可以建出一个严重左倾或者右倾的bst 但是，我们考虑算上虚边的整颗树我们会发现一个神奇的性质，无论是经过一条重的二叉树边还是虚边，所在子树的siz至少翻一倍，而这个性质在原来的线段树上是没有的 所以这个大bst的高度是$O(logn)$的 当然，这个bst既不能旋转也不能splay，所以维护区间信息会比较吃力，但是，我们为什么要维护区间信息呢？这是动态dp啊，我们只需要维护这整个重链的矩阵连乘积就行了……，所以维护整个重链的连乘积还是可以做到的 另外这个东西看起来听玄学其实比树剖还好写…… 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10; int n;int m;int v[2*N];int x[2*N];int ct;int al[N];int siz[N];int h[N];int we[N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} inline int dfs1(int u)//这里的树剖只需要一趟dfs求重儿子 { siz[u]=1;int mx=0; for(int i=al[u];i;i=x[i]) if(siz[v[i]]==0){siz[u]+=dfs1(v[i]);if(mx<siz[v[i]])mx=siz[v[i]],h[u]=v[i];} return siz[u]; } struct mar//矩阵类 { int mp[2][2]; mar(){mp[0][0]=mp[0][1]=mp[1][0]=mp[1][1]=-0x3f3f3f3f;} mar(int x){mp[0][0]=mp[1][1]=0;mp[1][0]=mp[0][1]=-0x3f3f3f3f;} friend mar operator *(mar a,mar b) { mar c;for(int i=0;i<2;++i) for(int k=0;k<2;++k) for(int j=0;j<2;++j)c.mp[i][j]=max(c.mp[i][j],a.mp[i][k]+b.mp[k][j]); return c; } inline int gmx(){return max(max(mp[0][0],mp[0][1]),max(mp[1][0],mp[1][1]));} inline int* operator [](const int& x){return mp[x];} }; struct bst { int s[N][2];int fa[N];int st[N];int tp;int lsiz[N];bool book[N];int root; mar mul[N];mar w[N];bst(){w[0]=mul[0]=mar(1);} inline void ud(const int& x){mul[x]=mul[s[x][0]]*w[x]*mul[s[x][1]];} inline void gtw(const int& x,const int& v) {w[x][1][0]+=mul[v].gmx();w[x][0][0]=w[x][1][0];w[x][0][1]+=max(mul[v][0][0],mul[v][1][0]);fa[v]=x;} inline void ih(){for(int i=1;i<=n;i++)w[i][0][1]=we[i],w[i][0][0]=w[i][1][0]=0;} inline bool isr(const int& p){return (s[fa[p]][1]!=p)&&(s[fa[p]][0]!=p);} inline int sbuild(const int& l,const int& r)//对序列建bst { if(l>r)return 0;int tot=0;for(int i=l;i<=r;i++)tot+=lsiz[st[i]]; for(int i=l,ns=lsiz[st[i]];i<=r;i++,ns+=lsiz[st[i]]) if(2*ns>=tot) { int rs=sbuild(l,i-1);int ls=sbuild(i+1,r);s[st[i]][0]=ls;s[st[i]][1]=rs; fa[ls]=st[i];fa[rs]=st[i];ud(st[i]);return st[i];//找重心递归建树 } } inline int build(int p)//链分治，每次处理一条链 { for(int t=p;t;t=h[t])book[t]=true; for(int t=p;t;t=h[t]) for(int i=al[t];i;i=x[i])if(!book[v[i]])gtw(t,build(v[i])); tp=0;for(int t=p;t;t=h[t])st[++tp]=t; for(int t=p;t;t=h[t])lsiz[t]=siz[t]-siz[h[t]];return sbuild(1,tp); } inline void modify(int p,int W)//修改，直接无脑修改上去就行了 { w[p][0][1]+=W-we[p];we[p]=W; for(int t=p;t;t=fa[t]) if(isr(t)&&fa[t])//如果是轻边 { w[fa[t]][0][0]-=mul[t].gmx();w[fa[t]][1][0]=w[fa[t]][0][0]; w[fa[t]][0][1]-=max(mul[t][0][0],mul[t][1][0]);ud(t); w[fa[t]][0][0]+=mul[t].gmx();w[fa[t]][1][0]=w[fa[t]][0][0]; w[fa[t]][0][1]+=max(mul[t][0][0],mul[t][1][0]); }else ud(t); } }bst; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&we[i]); for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);add(u,v);add(v,u);} dfs1(1);bst.ih();bst.root=bst.build(1); for(int i=1,p,w;i<=m;i++) {scanf("%d%d",&p,&w);bst.modify(p,w);printf("%d\n",bst.mul[bst.root].gmx());} return 0;//拜拜程序~ } ```