回溯实现dfs遍历中记录维护树上滑窗算法在树的 DFS 遍历中维护“窗口内不重复的颜色最近出现深度”动态调整窗口起点在一次遍历中高效求出满足“同色不重复”约束的最长路径树上滑窗·五步法同色不重复最长路径1. 建树把边转成无向邻接表存节点与边权2. 入栈DFS 进入节点时记录颜色上一次出现位置更新窗口左边界3. 算答案用前缀和算当前窗口路径长度更新最优解4. 递归遍历子节点维护路径和并回溯5.回溯恢复颜色位置与路径和保证不影响其他分支模板“路径上元素不重复/满足某种窗口约束”的问题可直接套用#include bits/stdc.husing namespace std;using ll long long;pairll, int treeSlidingWindow(int n,const vectorvectorpairint, int g, // 邻接表: {to, weight}const vectorint color // 每个节点的“颜色”/值) {pairll, int best {-1, 0}; // {max_length, start_depth}vectorll dis {0}; // 路径前缀和unordered_mapint, int last; // 颜色 - 上一次出现的深度 1functionvoid(int, int, int) dfs [](int u, int fa, int top_depth) {int c color[u];int old last[c];top_depth max(top_depth, old); // 窗口左边界更新// 更新最优解长度 当前前缀和 - 窗口起点前缀和ll len dis.back() - dis[top_depth];if (len best.first || (len best.first top_depth best.second)) {best {len, top_depth};}last[c] dis.size(); // 记录当前颜色位置for (auto [v, w] : g[u]) {if (v ! fa) {dis.push_back(dis.back() w);dfs(v, u, top_depth);dis.pop_back();}}last[c] old; // 回溯恢复};dfs(0, -1, 0);return best;}// 示例主函数int main() {int n;cin n;vectorint color(n);for (int i 0; i n; i) cin color[i];vectorvectorpairint, int g(n);for (int i 0; i n - 1; i) {int x, y, w;cin x y w;g[x].emplace_back(y, w);g[y].emplace_back(x, w);}auto [max_len, start_depth] treeSlidingWindow(n, g, color);cout max_len start_depth endl;return 0;}说明1. 核心思想在 DFS 遍历树时用last 哈希表记录每种颜色上一次出现的深度动态调整窗口左边界 top_depth 保证窗口内颜色不重复。2. 前缀和 dis 记录从根到当前节点的路径和用于快速计算窗口内路径长度。3. 时间复杂度每个节点访问一次哈希表操作平均 O(1)整体 O(n)。4. 可修改点- 若约束不是“同色不重复”可修改 last 的更新逻辑。- 若需要返回具体路径可在 DFS 中额外维护路径栈lc3425dfs 遍历树维护颜色最近出现深度和前缀和数组在 O(n) 时间内找到一条满足“同色不重复”的最长路径并返回其长度与起点深度这道题综合挺强的有树滑窗前缀和回溯这些都想到了还是超时还需要额外维护当前值上一次出现的深度来加快滑窗左端的移动速度...class Solution {public:vectorint longestSpecialPath(vectorvectorint edges, vectorint nums) {vectorvectorpairint, int g(nums.size());for (auto e : edges) {int x e[0], y e[1], w e[2];g[x].emplace_back(y, w);g[y].emplace_back(x, w);}pairint, int ans {-1, 0};vectorint dis {0};unordered_mapint, int last_depth;// 颜色 - 该颜色最近一次出现的深度 1注意这里已经 1 了auto dfs [](this auto dfs, int x, int fa, int top_depth) - void{int color nums[x];int old_depth last_depth[color];top_depth max(top_depth, old_depth);// 把 dis.size() - top_depth 取反这样 max 算的是最小值ans max(ans, pair(dis.back() - dis[top_depth], top_depth - (int) dis.size()));last_depth[color] dis.size();for (auto [y, w] : g[x]) {if (y ! fa) { // 避免访问父节点dis.push_back(dis.back() w);dfs(y, x, top_depth);dis.pop_back(); // 恢复现场}}last_depth[color] old_depth; // 恢复现场};dfs(0, -1, 0);return {ans.first, -ans.second};}};lc3486class Solution {vectorint nums;vectorvectorpairint, int g;pairint, int ans {-1, 0};vectorint dis {0};unordered_mapint, int last_depth;// 颜色 - 该颜色最近一次出现的深度 1注意这里已经 1 了// 对于本题dfs 写外面效率更高可能是 unordered_map 导致void dfs(int x, int fa, int top_depth, int last1) {int color nums[x];int last2 last_depth[color];top_depth max(top_depth, min(last1, last2)); // 相较 3425 题维护窗口左端点的逻辑变了ans max(ans, pair(dis.back() - dis[top_depth], top_depth - (int) dis.size()));last_depth[color] dis.size();for (auto [y, w] : g[x]) {if (y ! fa) {dis.push_back(dis.back() w);dfs(y, x, top_depth, max(last1, last2)); // 相较 3425 题额外维护 last1dis.pop_back();}}last_depth[color] last2;}public:vectorint longestSpecialPath(vectorvectorint edges, vectorint nums) {g.resize(nums.size());for (auto e : edges) {int x e[0], y e[1], w e[2];g[x].emplace_back(y, w);g[y].emplace_back(x, w);}this-nums nums;dfs(0, -1, 0, 0);return {ans.first, -ans.second};}};