学习了一下动态 DP
给定一棵 \(n\) 个节点的树, 点有点权, 有 \(m\) 次修改单点点权的操作, 回答每次操作之后的最大带权独立集大小.
首先一个显然的 \(O(nm)\) 的做法就是每次做一遍树形 DP(这也是我在 noip 考场上唯一拿到的部分分), 直接考虑如何优化这个东西.
简化一下问题, 假如这棵树是一条链, 那就变得很简单了, 可以直接拿线段树维护矩阵加速.
可是如果每个点不止有一个儿子呢?
我们首先树剖一下.
设 \(g[i][0]=\sum\limits_{j\in lightson} \max(f[j][0],f[j][1])\)
\(g[i][1]=a[i]+\sum\limits_{j\in lightson} f[j][0]\)
即 \(g[i][0]\) 表示 \(i\) 的所有轻儿子的 \(\max(f[j][0],f[j][1])\) 之和,\(g[i][1]\) 表示 \(i\) 的所有轻儿子的 \(g[j][0]\) 之和与 \(a[i]\) 的和.
那转移方程就可以改写为 \(f[i][0]=\max(g[i][0]+f[son[i]][0],g[i][0]+f[son[i]][1])\)
\(f[i][1]=g[i][1]+f[son[i]][0]\)
这就可以放在线段树上维护矩阵了.
即每个点维护一个 \(\quad\begin{matrix}g[i][0]&g[i][0]\\-\infty&g[i][1]\end{matrix}\). 然后在线段树上维护连乘积就好.
还有一点就是修改的时候, 要一直跳 \(top\), 可以这样理解: 假设当前更改了点 \(x\) 的点权, 那么就会改变 \(f[top[x]]\) 的值, 紧接着就会影响 \(g[fa[top[x]]]\) 的值, 所以我们要一直向上跳 \(top\) 修改才能维护好.
最后放一下代码:
- #pragma GCC optimize(2)
- #include<bits/stdc++.h>
- using std::min;
- using std::max;
- using std::swap;
- using std::vector;
- typedef double db;
- typedef long long ll;
- #define pb(A) push_back(A)
- #define pii std::pair<int,int>
- #define all(A) A.begin(),A.end()
- #define mp(A,B) std::make_pair(A,B)
- const int N=1e5+5;
- const int inf=1e9;
- #define ls x<<1
- #define rs x<<1|1
- #define lss ls,l,mid,ql,qr
- #define rss rs,mid+1,r,ql,qr
- int tot,dfn[N],top[N],end[N];
- int n,m,v[N],sze[N],son[N],f[N][2];
- int cnt,head[N],g[N][2],fa[N],fs[N];
- struct Edge{
- int to,nxt;
- }edge[N<<1];
- void add(int x,int y){
- edge[++cnt].to=y;
- edge[cnt].nxt=head[x];
- head[x]=cnt;
- }
- struct Mat{
- int a[3][3];
- Mat(){memset(a,0xcf,sizeof a);}
- friend Mat operator*(Mat x,Mat y){
- Mat z;
- for(int i=1;i<=2;i++)
- for(int k=1;k<=2;k++)
- for(int j=1;j<=2;j++)
- z.a[i][j]=max(x.a[i][k]+y.a[k][j],z.a[i][j]);
- return z;
- }
- }sum[N<<2],val[N];
- int getint(){
- int X=0,w=0;char ch=getchar();
- while(!isdigit(ch))w|=ch=='-',ch=getchar();
- while( isdigit(ch))X=X*10+ch-48,ch=getchar();
- if(w) return -X;return X;
- }
- void dfs(int now){
- sze[now]=1;
- for(int i=head[now];i;i=edge[i].nxt){
- int to=edge[i].to;
- if(sze[to]) continue;
- fa[to]=now;dfs(to);
- sze[now]=sze[to];
- son[now]=sze[son[now]]>sze[to]?son[now]:to;
- }
- }
- void dfs(int now,int low){
- dfn[now]=++tot;top[now]=low;fs[tot]=now;
- if(son[now]) dfs(son[now],low);
- for(int i=head[now];i;i=edge[i].nxt){
- int to=edge[i].to;
- if(dfn[to]) continue;
- dfs(to,to);
- g[now][0]+=max(f[to][0],f[to][1]);
- g[now][1]+=f[to][0];
- } if(son[now]) end[now]=end[son[now]];
- else end[now]=now;
- g[now][1]+=v[now];
- f[now][0]=g[now][0]+max(f[son[now]][0],f[son[now]][1]);
- f[now][1]=g[now][1]+f[son[now]][0];
- }
- void pushup(int x){
- sum[x]=sum[ls]*sum[rs];
- }
- void build(int x,int l,int r){
- if(l==r) return sum[x]=val[fs[l]],void();
- int mid=l+r>>1; build(ls,l,mid),build(rs,mid+1,r);
- pushup(x);
- }
- void init(){
- for(int i=1;i<=n;i++)
- val[i].a[1][1]=val[i].a[1][2]=g[i][0],val[i].a[2][1]=g[i][1],val[i].a[2][2]=-inf;
- build(1,1,n);
- }
- Mat query(int x,int l,int r,int ql,int qr){
- if(ql<=l and r<=qr) return sum[x];
- int mid=l+r>>1;
- if(qr<=mid) return query(lss);
- if(ql>mid) return query(rss);
- return query(lss)*query(rss);
- }
- Mat ask(int x){
- return query(1,1,n,dfn[top[x]],dfn[end[x]]);
- }
- void modify(int x,int l,int r,int ql,int qr){
- if(l==r) return sum[x]=val[fs[l]],void();
- int mid=l+r>>1;
- ql<=mid?modify(lss):modify(rss);
- pushup(x);
- }
- void change(int x,int y){
- val[x].a[2][1]+=y-v[x]; v[x]=y;
- Mat pre,nxt;
- while(x){
- pre=ask(x);
- modify(1,1,n,dfn[x],dfn[x]);
- nxt=ask(x);
- x=fa[top[x]];
- val[x].a[1][1]+=max(nxt.a[1][1],nxt.a[2][1])-max(pre.a[1][1],pre.a[2][1]);
- val[x].a[1][2]=val[x].a[1][1];
- val[x].a[2][1]+=nxt.a[1][1]-pre.a[1][1];
- }
- }
- signed main(){
- n=getint(),m=getint();
- for(int i=1;i<=n;i++) v[i]=getint();
- for(int i=1;i<n;i++){
- int x=getint(),y=getint();
- add(x,y),add(y,x);
- } dfs(1),dfs(1,1),init();
- while(m--){
- int x=getint(),y=getint();
- change(x,y);
- Mat ans=ask(1);
- printf("%d\n",max(ans.a[1][1],ans.a[2][1]));
- } return 0;
- }
然后两道例题:
BZOJ4712 洪水
题意
给出一棵树, 点有点权. 多次增加某个点的点权, 并在某一棵子树中询问: 选出若干个节点, 使得每个叶子节点到根节点的路径上至少有一个节点被选择, 求选出的点的点权和的最小值.
Sol
还是动态 DP.
先把 DP 式子列出来: \(f[i]=\min(a[i],\sum\limits_{j\in son[i]} f[j])\), 然后套路设 \(g[i]=\sum\limits_{j\in lightson[i]} f[j]\), 于是 \(f[i]=\min(a[i],g[i]+f[son[i]])\).
又可以写成矩阵相乘的形式:
\[ \begin{matrix}f[son[i]]\\0\end{matrix}\times \begin{matrix}g[i]&a[i]\\\infty&0\end{matrix}=\begin{matrix}f[i]\\0\end{matrix} \]
然后动态 DP 就行了.
需要注意一点的是在 \(change\) 函数里,\(pre,nxt\) 的矩阵应该是 \(ask(top[x])\) 而不是 \(ask(x)\).
NOIP2018 保卫王国
题意
给出一棵树, 点有点权. 每次强制选或不选两个节点, 求最小权覆盖集.
Sol
首先有个定理: 最小权覆盖集 = 全集 - 最大权独立集. 然后就是 luogu 模板题了.
来源: https://www.cnblogs.com/YoungNeal/p/10360291.html