首页 > 其他分享 >树形dp例题 + 学习笔记(入门版)

树形dp例题 + 学习笔记(入门版)

时间:2022-08-20 02:11:22浏览次数:97  
标签:结点 树上 入门 树形 例题 dp

树形dp,即在树上进行dp。

需要对树这一数据结构有清晰的了解。其中重点在于树的遍历、子树相关问题。

难点常常在于状态方程的书写。

例题

一、没有上司的舞会

题意
树上每个结点有权值,要求在树上选一些点,满足有父子关系的结点只能出现一个,问选出的最大的权值和。

思路
用 \(dp[i][0/1]\) 表示 第 \(i\) 号结点选或者不选,令 \(x \in son[i]\) ,方程为

\(dp[i][0] += max(dp[x][0],dp[x][1])\) ,

\(dp[i][1] += dp[x][0]\)

标签:结点,树上,入门,树形,例题,dp
From: https://www.cnblogs.com/re0acm/p/16607044.html

相关文章

  • 状压DP-1815. 得到新鲜甜甜圈的最多组数
    问题描述有一个甜甜圈商店,每批次都烤 batchSize 个甜甜圈。这个店铺有个规则,就是在烤一批新的甜甜圈时,之前所有 甜甜圈都必须已经全部销售完毕。给你一个整数batchSi......
  • 【DP】#1109. [POI2007]堆积木Klo
    https://darkbzoj.cc/problem/1109分析考虑状态表示原来在位置\(i\)的数有贡献(也就是说在结束操作后它的位置\(i'\)满足\(i'=w_i\))的最大值为\(f[i]\)。那么我们......
  • 如何使用 K3s 部署 Wordpress
    为什么使用K3s部署Wordpress很多朋友使用Docker或者宝塔来部署Wordpress,如果只有一台服务器,这样搞没问题。不过我建议使用K3s部署Wordpress,因为这样才能享受......
  • Dp的优化
    Dp的优化单调栈优化DpTheGreatWallII题意:给你n个点,问分成1∼n组,每一组的代价就是这一组中的最大值,问每一种情况的最小权值和。思路:把状态定义为dij表示......
  • 千兆以太网_发送模块设计_udp_rgmii_tx
    功能:在FPGA开发板上,用户数据存于FIFO,经过UDP,IP,MAC封装,通过RGMII接口发送出去。完整的以太网应该包括收发功能,这里介绍发送模块。实现:序列机过程:发送顺序:  MAC帧头—......
  • 【kuangbin】专题十二 基础DP1
    【kuangbin】专题十二基础DP1https://vjudge.net/contest/68966#overview前几周写了来着,忘更了我饿了,先放代码,吃完再来A-MaxSumPlusPlus#include<bits/stdc++.......
  • 压缩空间尝试使用只与前一个状态有关的dp dp[2][N]
    之后每次迭代t^1使得0->11->0这里有n个世界,每个世界都有m个点。在i个世界中,你最多可以选择一条边,从u点移动到v点(可以选择不移动)。随后进入到第i+1个世界......
  • 扑克牌(期望DP)
    题意Rainbow把一副扑克牌(\(54\)张)随机洗开,倒扣着放成一摞。然后Admin从上往下依次翻开每张牌,每翻开一张黑桃、红桃、梅花或者方块,就把它放到对应花色的堆里去。Rainb......
  • 【DP 记录】AcWing 734. 能量石
    传送门给你几个物品,每种选一次,求最大价值,首先想到01背包,但是我们遇到了一个问题:普通的01背包在选择物品时是不讲求顺序的,但在这道题中,物品的选择是有顺序的(即对最优......
  • 递归遍历书树形数据获取父级key
    结果vardata=[{"key":"sub1","children":[{......