树上滑窗
回溯实现，dfs遍历中记录维护
树上滑窗算法，在树的 DFS 遍历中，维护“窗口内不重复的颜色最近出现深度”，动态调整窗口起点，在一次遍历中高效求出满足“同色不重复”约束的最长路径
树上滑窗·五步法（同色不重复最长路径）
1. 建树：把边转成无向邻接表，存节点与边权
2. 入栈：DFS 进入节点时，记录颜色上一次出现位置，更新窗口左边界
3. 算答案：用前缀和算当前窗口路径长度，更新最优解
4. 递归：遍历子节点，维护路径和并回溯
5.回溯：恢复颜色位置与路径和，保证不影响其他分支
模板
“路径上元素不重复/满足某种窗口约束”的问题，可直接套用：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<ll, int> treeSlidingWindow(
int n,
const vector<vector<pair<int, int>>>& g, // 邻接表: {to, weight}
const vector<int>& color // 每个节点的“颜色”/值
) {
pair<ll, int> best = {-1, 0}; // {max_length, start_depth}
vector<ll> dis = {0}; // 路径前缀和
unordered_map<int, int> last; // 颜色 -> 上一次出现的深度 + 1
function<void(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;
vector<int> color(n);
for (int i = 0; i < n; ++i) cin >> color[i];
vector<vector<pair<int, 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 中额外维护路径栈
lc3425
dfs 遍历树，维护颜色最近出现深度和前缀和数组
在 O(n) 时间内找到一条满足“同色不重复”的最长路径，并返回其长度与起点深度
这道题综合挺强的，有树，滑窗，前缀和，回溯
这些都想到了还是超时，还需要额外维护当前值上一次出现的深度来加快滑窗左端的移动速度...
class Solution {
public:
vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
vector<vector<pair<int, 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);
}
pair<int, int> ans = {-1, 0};
vector<int> dis = {0};
unordered_map<int, 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};
}
};
lc3486
class Solution {
vector<int> nums;
vector<vector<pair<int, int>>> g;
pair<int, int> ans = {-1, 0};
vector<int> dis = {0};
unordered_map<int, 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 题，额外维护 last1
dis.pop_back();
}
}
last_depth[color] = last2;
}
public:
vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& 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};
}
};