CF round 867(#Div 3) F.Gardening Friends (dfs + 换根dp)

题目大意:  有棵树以1为根结点，每条边长度都是k, 定义树的cost为离树根最远的点到树根的距离, 一次操作可以花费c将树根移到树根任意一个相邻点, 利润为树此时的cost减去形成该树的操作花费, 输出最大利润。

不难想到一个暴力枚举的算法, 也就是枚举每一个根节点 n, 然后计算最远距离更新答案, 时间复杂度为 O()， 超时。。。

那么怎么把时间复杂度降下来呢？ 我们可以把树看作成一个无向图, 然后可以使用换根dp, 先定义我们的状态表示的集合

dp[u][0]: 以 u 为根节点时向下走的最大距离

dp[u][1]: 以 u 为根节点时向下走的第二大距离

我们利用 换根 dp 的思想先计算出题目中任意 u 为 根节点先下中的情况, 也就是 dp[u][0], dp[u][1], 这可以使用 dfs 来实现。

换根 dp 的思想就是更新每次换根节点时对答案的贡献。

接下来我们来推导状态转移方程, 假设我们从 父节点 fa 换根到子节点 u, 此时想得到最大距离无非就两条路径: 向上走或者向下走

我们先考虑向下走的情况, 很明显为 dp[u][0]

我们考虑向上走的情况, 假设最大距离为 len, 为了避免路径重新经过 u, 会有两种情况:

当从 父节点 fa 向下走得到最大距离路径中不包含 u 时:

len = max(dp[fa][0], len_fa) + 1

当从 父节点 fa 向下走得到最大距离路径中包含 u 时, 由于路径重新经过 u 会时答案变得没有意义，我们需要换条次大的路径:

len = max(dp[fa][1], len_fa) + 1

我们在递归时可以使用变量 cnt 定义为换根的次数。

于是更新答案: ans = max(ans, max(dp[u][0], len) * k - c * cnt)

时间复杂度O(n) 代码:

解法参考自: https://zhuanlan.zhihu.com/p/624893947