LC 3425. Longest Special Path

https://leetcode.com/problems/longest-special-path/description/

class Solution {
public:
    int ansValue, ansLen;
    void dfs(int pre, int cur, int curDep, vector<vector<pair<int, int>>> &g, vector<int> &nums, vector<int> &arr, int l, unordered_map<int, int> &dep) {
        int prevDep = 0;
        if (dep.count(nums[cur])) prevDep = dep[nums[cur]];
        dep[nums[cur]] = curDep;

        l = max(l, prevDep);
        int curValue = arr.back() - arr[l];
        int curLen = curDep - l;
        if (ansValue < curValue || (ansValue == curValue && curLen < ansLen)) {
            ansValue = curValue;
            ansLen = curLen;
        }
        for (auto [nxt, val]: g[cur]) {
            if (nxt == pre) continue;
            arr.push_back(arr.back() + val);
            dfs(cur, nxt, curDep + 1, g, nums, arr, l, dep);
            arr.pop_back();
        }
        dep[nums[cur]] = prevDep;
    }

    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        ansValue = 0, ansLen = 1;
        int n = nums.size();
        vector<vector<pair<int, int>>> g(n);
        for (auto &x: edges) {
            g[x[0]].push_back({x[1], x[2]});
            g[x[1]].push_back({x[0], x[2]});
        }
        vector<int> arr;
        unordered_map<int, int> cnt;
        arr.push_back(0);
        cnt[nums[0]] = 0;
        dfs(-1, 0, 1, g, nums, arr, 0, cnt);
        return {ansValue, ansLen};
    }
};

Tag: Tree, DFS, Sliding Window

本題的考點在樹上做 Sliding Window，透過題目可以知道他挺符合 Sliding Window 的樣子，也就是在一個 Window 當中不可以存在相同的數字。

這裡還有一個難點是在需要使用 prefix sum 來知道一個區間內的總合，同時需要紀錄一個 left 值來與當前往前跳的進行比較，才會知道到底最前面是到哪裡。