请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

leetCode 2925. 在树上执行操作以后得到的最大分数 + 正则难反 + 树形 DP

2023-11-23

2925. 在树上执行操作以后得到的最大分数 - 力扣(LeetCode)

有一棵 n 个节点的无向树,节点编号为 0  n - 1 ,根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。

同时给你一个长度为 n 下标从 0 开始的整数数组 values ,其中 values[i] 表示第 i 个节点的值。一开始你的分数为 0 ,每次操作中,你将执行:

  • 选择节点 i 。
  • 将 values[i] 加入你的分数。
  • 将 values[i] 变为 0 。

如果从根节点出发,到任意叶子节点经过的路径上的节点值之和都不等于 0 ,那么我们称这棵树是 健康的 。你可以对这棵树执行任意次操作,但要求执行完所有操作以后树是 健康的 ,请你返回你可以获得的 最大分数 。

输入:edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出:11
解释:我们可以选择节点 1 ,2 ,3 ,4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] + values[2] + values[3] + values[4] + values[5] = 11 。11 是你对树执行任意次操作以后可以获得的最大得分之和。

输入:edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
输出:40
解释:我们选择节点 0 ,2 ,3 和 4 。
- 从 0 到 4 的节点值之和为 10 。
- 从 0 到 3 的节点值之和为 10 。
- 从 0 到 5 的节点值之和为 3 。
- 从 0 到 6 的节点值之和为 5 。
所以树是健康的。你的得分之和为 values[0] + values[2] + values[3] + values[4] = 40 。
40 是你对树执行任意次操作以后可以获得的最大得分之和。

(方法一)参考灵神这篇文章:2925. 在树上执行操作以后得到的最大分数 - 力扣(LeetCode) 

思路分析:题目中“如果从根节点出发,到任意叶子节点经过的路径上的节点值之和都不等于 0”。所在在执行操作时,每条从根节点到叶子节点的路径上,都存在一个节点不去操作(多条路径可能共用一个不操作的节点)

  • 为了使得分数最大,不操作的节点之和应尽可能地小

定义一棵以 u 为根节点的健康子树:

  • ① 要么不操作根节点 u ,此时这棵树是健康的,剩余的所有子节点都可以操作
  • ② 要么操作根节点 u ,但是 u 的所有子树都需要保证自己是健康的

要得到最小和,取其两者情况的最小值

建图:

int n = values.size();
vector<vector<int>> g(n);
g[0].push_back(-1); // 避免误把根节点当作叶子
for(auto &e:edges) {
    int x = e[0], y = e[1];
    g[x].push_back(y);
    g[y].push_back(x);
}

class Solution {
public:
    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
        int n = values.size();
        vector<vector<int>> g(n);
        g[0].push_back(-1); // 避免误把根节点当作叶子
        for(auto &e:edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        // dfs(x,fa) 计算以 x 为根的子树是健康时,失去的最小分数
        function<long long(int,int)> dfs = [&](int x,int fa)-> long long {
            if(g[x].size() == 1) { // x 是叶子
                return values[x];
            }
            long long loss = 0; // 第二种情况
            for(int y:g[x]) {
                if(y!=fa) {
                    loss+=dfs(y,x);// 计算以 y 为根的子树是健康时,失去的最小分数
                }
            } 
            return min((long long) values[x],loss); // 两种情况取最小值
        };
        long long sum = accumulate(values.begin(),values.end(),0LL);
        return sum - dfs(0,-1);
    }
};

复杂度分析

  • 时间复杂度:O(n),其中 n 为 values 的长度
  • 空间复杂度:O(n)

(方法二)参考sad_path这篇文章2925. 在树上执行操作以后得到的最大分数 - 力扣(LeetCode)

class Solution {
public:
    class Node{
    public:
        Node(long x,int i) : val(x),index(i){}
    public:
        long val;
        int index;
    public:
        list<Node*> childArr;
    };
    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
        int n = values.size();
        // 建树,实际上是建图
        vector<Node *> nodes;
        for(int i=0;i<n;i++) {
            nodes.push_back(new Node(values[i],i));
        }
        for(auto &e:edges) {
            int x = e[0], y = e[1];
            nodes[x]->childArr.push_back(nodes[y]);
            nodes[y]->childArr.push_back(nodes[x]);
        }
        vector<bool> visited(n,false);
        visited[0] = true;
        long long sum = accumulate(values.begin(),values.end(),0LL);
        long long Min = dfs(nodes[0], visited);
        return sum - Min;
    }

    long long dfs(Node* root,vector<bool> visited) {
        int count = 0;
        long Min = 0;
        for (Node* child : root->childArr) {
            if (visited[child->index]) {
                count++;
                continue;
            }
            visited[child->index] = true;
            Min += dfs(child, visited);
            visited[child->index] = false;
        }
        // 此时该节点为叶节点,直接返回它的 val
        if (count == root->childArr.size()) {
            return root->val;
        }
        return min(root->val, Min);
    }
};

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部