lc/3786/

[giscus[bot]]

lc/3786/

多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

https://leetcode.doocs.org/lc/3786/

[meetkool]

#include
#include
using namespace std;

class Solution {
vector adj[100005], down, res;
vector vals;

void dfs_down(int u, int p) {
    down[u] = vals[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_down(v, u);
        if (down[v] > 0) down[u] += down[v];
    }
}

void dfs_up(int u, int p, int up_val) {
    res[u] = down[u] + max(0, up_val);
    for (int v : adj[u]) {
        if (v == p) continue;
        // Best from parent including sibling branches
        int take_from_parent = res[u] - (down[v] > 0 ? down[v] : 0);
        dfs_up(v, u, take_from_parent);
    }
}

public:
vector maxSubgraphScore(int n, vector<vector>& edges, vector& good) {
down.assign(n, 0); res.assign(n, 0); vals.assign(n, 0);
for(int i=0; i<n; i++) {
vals[i] = (good[i] == 1 ? 1 : -1);
adj[i].clear();
}
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
dfs_down(0, -1);
dfs_up(0, -1, 0);
return res;
}
};

[meetkool]

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    vector<int> adj[100005], down, res;
    vector<int> vals;

    void dfs_down(int u, int p) {
        down[u] = vals[u];
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs_down(v, u);
            if (down[v] > 0) down[u] += down[v];
        }
    }

    void dfs_up(int u, int p, int up_val) {
        res[u] = down[u] + max(0, up_val);
        for (int v : adj[u]) {
            if (v == p) continue;
            // Best from parent including sibling branches
            int take_from_parent = res[u] - (down[v] > 0 ? down[v] : 0);
            dfs_up(v, u, take_from_parent);
        }
    }

public:
    vector<int> maxSubgraphScore(int n, vector<vector<int>>& edges, vector<int>& good) {
        down.assign(n, 0); res.assign(n, 0); vals.assign(n, 0);
        for(int i=0; i<n; i++) {
            vals[i] = (good[i] == 1 ? 1 : -1);
            adj[i].clear();
        }
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        dfs_down(0, -1);
        dfs_up(0, -1, 0);
        return res;
    }
};