MyLeetcode/cpp_solutions/2467.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    void bobDfs(int parent, int node, vector<vector<int>>& adjacency, vector<int>& bobPath, vector<int>& currentPath) {
        if (node == 0) {
            bobPath = currentPath;
            return;
        }
        for (auto& neighbor : adjacency[node]) {
            if (neighbor == parent) continue;
            currentPath.push_back(neighbor);
            bobDfs(node, neighbor, adjacency, bobPath, currentPath);
            currentPath.pop_back();
        }
    }
    void aliceDfs(int parent, int node, vector<vector<int>>& adjacency, int& res, int income, vector<int>& nodeTime, int time, vector<int>& amount) {
        if (nodeTime[node] == time) {
            income += amount[node] / 2;
        }
        else if (nodeTime[node] == -1 || nodeTime[node] > time){
            income += amount[node];
        }
        else {
            income += 0;
        }

        int cnt = 0;
        for (auto& neighbor : adjacency[node]) {
            if (neighbor == parent) continue;
            aliceDfs(node, neighbor, adjacency, res, income, nodeTime, time + 1, amount);
            cnt++;
        }

        // cnt == 0 => leaf
        if (cnt == 0) {
            res = max(res, income);
        }
    }
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = edges.size() + 1;
        vector<vector<int>> adjacency(n);
        for (auto& edge : edges) {
            adjacency[edge[0]].push_back(edge[1]);
            adjacency[edge[1]].push_back(edge[0]);
        }

        // bob to root by dfs
        vector<int> bobPath;
        vector<int> currentPath;
        currentPath.push_back(bob);
        bobDfs(-1, bob, adjacency, bobPath, currentPath);

        // get time
        int m = bobPath.size();
        vector<int> nodeTime(n, -1);
        for (int i = 0; i < m; ++i) {
            nodeTime[bobPath[i]] = i;
        }

        // alice
        int res = INT_MIN;
        aliceDfs(-1, 0, adjacency, res, 0, nodeTime, 0, amount);
        return res;
    }
};