动态规划之卖树

问题描述

小蓝和小桥是两位花园爱好者，她们在自己的花园里种了一棵n个节点的树，每条边的长度为k。初始时，根节点为1号节点。她们想把这棵树卖掉，但是想卖个好价钱。树的价值被定义为根节点到所有节点的路径长度的最大值。

为了让这棵树更有价值，小蓝和小桥可以对这棵树进行一种操作：花费c的代价，将根节点从当前的节点移动到它的一个相邻节点上。注意，这个操作不会改变树的形态，只是改变了根节点的位置。

她们希望通过尽可能地进行操作，使得卖出去的这棵树的盈利最大。盈利被定义为卖出去的树的价值减去操作的总代价。

请你帮助她们，找出她们能够获得的最大盈利。

输入格式

第一行包含一个整数t,表示测试数据组数。

每组数据第一行包含三个整数n、k和c,表示树的节点数、每条边的长度和进行一次移动操作的代价。

接下来n-1行，每行描述树的一条边，包含两个整数ui和vi,表示树中连接ui和vi之间的一条边。

输出格式

对于每组数据，输出一个整数，表示最大盈利。

样例输入

4

32

2

3

21

31

541

21

42

54

34

653

41

61

26

51

32

1064

13

19

97

76

64

92

28

85

510

样例输出

2

12

17

32

一、信息（题目的有用信息）

这个问题是关于在一棵树上进行操作以最大化盈利的问题。关键信息如下：

1. 树的结构：树共有n个节点，每条边的长度为k。
2. 操作定义：通过花费c的代价，可以将根节点移动到其相邻的节点。
3. 价值定义：树的价值等于根节点到所有节点的路径长度的最大值。
4. 盈利计算：盈利等于树的价值减去操作的总代价。
5. 目标：通过操作使得盈利最大化。

二、分析

每个信息的作用

1. 树的结构和操作定义：这决定了问题的解决需要考虑树的形态和根节点的选择。
2. 价值和盈利计算：提供了盈利最大化的目标和计算方法。

思考过程和分析过程

• 树的深度与价值：树的价值由最远的叶节点决定。因此，将根节点移动到距离叶节点更近的位置可以增加树的价值。
• 操作的代价与盈利：每次操作都有代价，需要权衡操作带来的价值提升和代价之间的关系。
• 最大化盈利：找到一种策略，使得在增加价值和减少代价之间达到最佳平衡。

策略

• 找到最深的叶节点：确定距离原始根节点最远的叶节点。
• 计算移动代价：计算将根节点移动到该叶节点的路径上某个节点的代价。
• 比较盈利：对于每个可能的新根节点，计算移动后的盈利，并找到盈利最大的位置。

三、算法设计

1. 深度优先搜索（DFS）：遍历树以找到最深的叶节点和路径。
2. 计算最大盈利：
   • 对于每个可能的新根节点，计算移动后的树的价值和操作代价。
   • 选择最大化盈利的操作。

四、代码实现（用C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAXN = 100005;
vector<int> g[MAXN];
int maxDepth, farthestNode;
long long maxProfit;
 
void dfs(int u, int p, int depth, long long k, long long c) {
    if (depth > maxDepth) {
        maxDepth = depth;
        farthestNode = u;
    }
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u, depth + 1, k, c);
        }
    }
}
 
void solve(int n, long long k, long long c) {
    maxDepth = -1;
    dfs(1, 0, 0, k, c);
    maxProfit = max(0LL, k * maxDepth - c * (maxDepth - 1));
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long k, c;
        cin >> n >> k >> c;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        solve(n, k, c);
        cout << maxProfit << endl;
    }
    return 0;
}

五、实现代码过程中可能遇到的问题

1. 内存和时间限制：确保算法在给定的内存和时间限制下有效。
2. 树的表示：合理地表示树结构，以便于遍历和操作。
3. 边界条件：处理树只有一个节点的特殊情况。
4. 数值溢出：当n、k和c的值很大时，可能会导致计算过程中的数值溢出。需要使用足够大的数据类型来存储和计算。
5. 递归深度：在深度优先搜索中，可能需要处理大规模数据导致的深递归调用。