题意：给定一个 $n$ 个点 $m$ 条边的无向无环图，在尽量少的节点上放灯，使得所有边都与灯相邻(被灯照亮)。在灯的总数最小的前提下，被两盏灯同时照亮的边数应该尽可能大。

还是树形 DP。

这道题有两个限制条件：第一条件为灯的总数最小，第二条件为被两盏灯同时照亮的边数最大。

发现限制条件既包括最小又包括最大，不好转移，我们尝试改变第二个条件，即变成只被一盏灯照亮的边最小，这样两个限制条件就都是最小了。因此我们把放的灯数 $x$ 和只被一盏灯照亮的边数 $y$ 的量放在一起处理，由于第一条件比第二条件影响更大，我们把它们的花费 $m$ 设为 $kx+y$ ($k$ 是一个足够大的值，大于 $y$ 的总和，否则会使得 $y$ 影响到 $x$)，这样既可以便于直接从 $m$ 中直接得出 $x$ 和 $y$，同时也利于转移。

题意：给出一个 $n$ 个点，$m$ 条边的无向图，每条边上是有颜色的。有 $q$ 组询问。对于第 $i$ 组询问，给出点对 $u_i,v_i$， 求有多少种颜色 $c$，满足存在至少一条从 $u_i$ 到 $v_i$ 的路径，使得该路径上的所有边的颜色均为 $c$。

暴力分块！！！

对于不同的数据采取不同的暴力方式，即可通过这道题。

题意：小 $\text{A}$ 和小 $\text{B}$ 决定利用假期外出旅行，他们将想去的城市从 $1$ 到 $n$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为 $h_i$，城市 $i$ 和城市 $j$ 之间的距离 $d_{i,j}$ 恰好是这两个城市海拔高度之差的绝对值，即 $d_{i,j}=|h_i-h_j|$。

题意：$n$ 个物品，每个物品都有贡献值 $p _{i}$。物品分为基础物品和高级物品。基础物品的价格为 $val _{i}$，数量限制为 $l _{i}$；高级物品不需要额外花费，需要不同种不同数量的低级物品合成。现在你有 $m$ 个金币，如何购买和合成物品使贡献值最大。

经典的 树 上 背 包 ！！！

题意：有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他 的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

一道经典的树形 DP。