LeetCodePro/3486.longest-special-path-ii.cpp at main · Lh-Liang/LeetCodePro · 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#
# @lc app=leetcode id=3486 lang=cpp
#
# [3486] Longest Special Path II
#
# @lc code=start
class Solution {
public:
    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        int n = nums.size();
        vector<vector<pair<int, int>>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back({e[1], e[2]});
            adj[e[1]].push_back({e[0], e[2]});
        }

        vector<long long> dist = {0};
        unordered_map<int, int> last;
        unordered_map<int, int> secondLast;

        long long maxLen = 0;
        int minNodes = 1;

        function<void(int, int, long long, int, int)> dfs = [&](int u, int parent, long long d, int left, int boundary) {
            int idx = dist.size() - 1;
            int v = nums[u];

            int oldLast = last.count(v) ? last[v] : -1;
            int oldSecondLast = secondLast.count(v) ? secondLast[v] : -1;

            int prevOcc = oldLast;
            int secondPrevOcc = oldSecondLast;

            // Handle "3 occurrences" constraint
            if (secondPrevOcc >= left) {
                left = secondPrevOcc + 1;
            }

            // Recheck boundary validity
            if (boundary < left) {
                boundary = -1;
            }

            // Handle "at most one duplicate" constraint
            if (prevOcc >= left) {
                if (boundary >= left) {
                    // Two duplicates, remove the older one
                    if (boundary < prevOcc) {
                        left = max(left, boundary + 1);
                        boundary = (prevOcc >= left) ? prevOcc : -1;
                    } else {
                        left = max(left, prevOcc + 1);
                        boundary = (boundary >= left) ? boundary : -1;
                    }
                } else {
                    boundary = prevOcc;
                }
            }

            // Update tracking
            if (oldLast >= 0) {
                secondLast[v] = oldLast;
            }
            last[v] = idx;

            // Update answer
            long long pathLen = d - dist[left];
            int nodeCount = idx - left + 1;
            if (pathLen > maxLen || (pathLen == maxLen && nodeCount < minNodes)) {
                maxLen = pathLen;
                minNodes = nodeCount;
            }

            // Recurse
            for (auto& [next, w] : adj[u]) {
                if (next != parent) {
                    dist.push_back(d + w);
                    dfs(next, u, d + w, left, boundary);
                    dist.pop_back();
                }
            }

            // Backtrack
            if (oldLast >= 0) {
                last[v] = oldLast;
            } else {
                last.erase(v);
            }

            if (oldSecondLast >= 0) {
                secondLast[v] = oldSecondLast;
            } else {
                secondLast.erase(v);
            }
        };

        dfs(0, -1, 0, 0, -1);

        return {(int)maxLen, minNodes};
    }
};
# @lc code=end