做了好久的树形 DP(大雾) ,(noip)csp-s 考了好多树形 DP
树形 DP 基本分为这几种
1. 最大独立集 (没有上司的舞会)
经典树形 DP
\(dp[i][0/1]\) 表示 i 这个点选与不选.
- \(dp[u][0] += dp[v][1];\)
- \(dp[u][1] += max(dp[v][0],dp[v][1]);\)
2. 最小点覆盖 (战略游戏)
状态与上面一样
- \(dp[u][0] += dp[v][1];\)
- \(dp[u][1] += min(dp[v][0],dp[v][1]);\)
3. 最小支配集 (SDOI 保安站岗)
\(dp[i][0/1/2]\) 表示这个点被自己覆盖, 被儿子覆盖, 被父亲覆盖
- \(dp[u][0] += min(dp[v][0],dp[v][1],dp[v][2]);\)
- \(dp[u][1] += min(dp[v][1],dp[v][0]);\)
- (注: 如果 u 所有的儿子 v 的 dp[v][1] <dp[v][0] 强制选一个最小的 dp[v][0]);
- \(dp[u][2] += min(dp[v][0],dp[v][1]);\)
- int dt=1e9+7,cnt=0;f[u][1]=pa[u];
- for(int p=last[u];p;p=pre[p])
- {
- int v=other[p];
- if(v==fa)continue;
- dfs(v,u);
- }
- for(int p=last[u];p;p=pre[p])
- {
- int v=other[p];
- if(v==fa)continue;
- f[u][1]+=min(min(f[v][2],f[v][1]),f[v][0]);
- f[u][2]+=min(f[v][1],f[v][0]);
- if(f[v][1]<f[v][0])cnt = 1;
- else dt=min(dt,f[v][1]-f[v][0]);
- f[u][0]+=min(f[v][1],f[v][0]);
- }
- if(cnt==0)
- f[u][0]+=dt;
- 4.Computer
求树上每个点到最远点的距离
\(dp[i][0/1/2]\) 分别表示子树内最长链, 次长链, 子树外最长链
- inline void dfs1(int x,int fa)
- {
- int fis = 0 ,sec = 0;
- for(int p = last[x];p;p = pre[p])
- {
- int v = other[p];
- if(v == fa)continue;
- dfs1(v,x);
- int tmp = dp[v][0] + len[p];
- if(tmp>= fis)
- sec = fis,fis = tmp;
- else if(tmp> sec)
- sec = tmp;
- }
- dp[x][0] = fis;dp[x][1] = sec;
- }
- inline void dfs2(int x,int fa)
- {
- for(int p = last[x];p;p = pre[p])
- {
- int v = other[p];
- if(v == fa)continue;
- if(dp[v][0] == dp[x][0] - len[p])
- dp[v][2] = len[p] + max(dp[x][1],dp[x][2]);
- else
- dp[v][2] = len[p] + max(dp[x][2],dp[x][0]);
- dfs2(v,x);
- }
- }
5. 树上背包 (选课, 有线电视网)
\(dp[i][j]\) 表示子树 i 中选了 j 门课
- $ dp[u][j] = max(dp[u][j],dp[v][j-k] + dp[u][k]) $
- for(int p=last[u];p;p=pre[p])
- {
- int v=other[p];
- for(int i=m+1;i>=1;i--)
- {
- for(int j=i;j>=1;j--)
- if(f[u][j]>=0&&f[v][i-j]>=0)
- f[u][i]=max(f[u][i],f[u][j]+f[v][i-j]);
- }
- }
复杂度 \(O(nm^{2})\)
用 dfn 序优化之后就是 \(O(nm)\)
树上背包基本都是这个套路
特别的像 HAOI 树上染色一题
- for(int i = min(siz[u],k) ; i>= 0 ;i--)
- {
- for(int j = 0; j <= min(siz[v],i);j++)
- {
- if(f[u][i-j] == -1)continue;
- ll val = (ll)(k-j)*j*len[p] + (ll)(siz[v]-j)*(n-k-siz[v]+j)*len[p];
- f[u][i] = max(f[u][i],f[v][j] + f[u][i-j] + val);
- }
- }
取 min 的两个位置要特别注意, 如果不取 min 的话复杂度就是错的, 这其中的道理不好分析, 但这样做完之后, 复杂度就是 \(O(n^{2})\)
总结
树形 DP 多数分为 \(dp[i][0/1]\), 和背包几种类型, 主要考虑子树中对当前点的贡献, 或者子树外对当前点的贡献, 来写出方程.
来源: http://www.bubuko.com/infodetail-3394389.html