题面 P3233 [HNOI2014]世界树 Solution 这是一道虚树妙题。 我们不妨先考虑一下每一次$O(n)$计算的暴力怎么做。 $O(n\cdot m)$的暴力肥肠简单，我们只需要做两遍dfs。考虑设$f[i]$表示离$i$最近的聚居地是什么，$MIN[i]$表示$i$到最近的聚居地的距离。我们第一遍dfs先找出$i$到它子树内的聚居地的最小距离，之后再做一遍dfs来找$i$往祖先方向后头走能走到的最近聚居地的距离即可。 观察数据范围后发现，$\sum m<=300000$，因此考虑使用虚树。 建…

题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先，我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是，仔细观察那张收费表格后会发现，我们可以重新定义一下这个收费：我们假设路由器节点的颜色为叶子中数目较多的颜色，当一个叶子结点颜色与路由器节点颜色相同的时候不收钱，否则收一份钱。我们可以惊讶的发现，这样做之后我们的新收费做法就与原来题目要求的重合了，而且贡献由点对转到了点上。 接下来，我们就可以统计每个叶子节点对每个路由器产生的贡献了。我们设$F[i][j]$表示第$i$个叶子节…

题面 4438 [HNOI/AHOI2018]道路 Solution 这是一道树形DP妙题。 平时，我们设计树形DP的状态一般都是以子树为基础来设计的。很不幸的是，这题因为那个蜜汁柿子无法化简，导致了极其严重的后效性。因此，我们这里并不能以子树为基础来设计状态了。 这题妙就妙在这个状态设计。这题我们考虑以链为基础来设计状态。 设$f[i][j][k]$表示从根节点到达第$i$个点，一路上经过了$j$条没有修过的公路及$k$条没有修过的铁路，把它的孩子全部连同到根所需的最小代价。 这样一来，我们惊讶的发现这样设就没有…

题面 传送门：洛谷 Solution 这是一道十分经典的树形DP题，这种类型的树形DP有一种很普遍的解法。 首先，观察题目，我们把这道题转换一下：给定一颗树，选出包含1号节点（根)的一颗子树，使得点权和最大。 我们可以这样子定义状态： 设$f[i][j]$ 表示以i为根节点的子树，选出j个节点，所能达到的最大点权值。 对于二叉树来说，转移很显然，就是枚举左子树分配多少个节点，就可以对应的得出右子树能分配到多少个节点，对所有情况取最大值就好。 对于多叉树来说，问题就没有那么简单了，这里，我们有两个方案可以解决这个问题…

题面 传送门：洛谷 Solution 这是一道简单的树形DP题。 首先，我们可以转换一下题面，可以发现，题目要求我们求出一颗树上的最大联通子图。 因为我们是在树上取的，实际上就是取一颗子树。 这个就是最基础的树形DP模型了。 我们可以设f[i]表示我们选的子图以i为根所能取的子树的最大值。 转移是： $f[i] = beauty[i] + xigema(max(f[j],0))$ （也就是一颗树的孩子所能取的子树，如果它孩子为根的子树>0，就取它，否则不取） 答案就是最大的$f[i]$ Code //Luogu P…