题意简述

给定一棵树，每个点有权值 $v_i$。 对每个点 $u$，求所有经过 $u$ 且边数在 $[L,R]$ 之间的简单路径中，路径点权和的最大值 $f_u$。 如果不存在这样的路径，输出一个固定的大负数。

关键观察

路径表示 一条简单路径可以看作由 $u$ 分割成两条向下（或向上）的路径拼接而成。

点权和与边数 设路径长度为边数 $k$，则点数为 $k+1$，点权和为路径上所有点的 $v_i$ 之和。

问题转化 对于每个点 $u$，我们要求：

f u

max ⁡ L ≤ k ≤ R

max ⁡ 经过 u 的路径 P sum ( P ) f u ​

L≤k≤R max ​

经过 u 的路径 P max ​ sum(P) 其中 $k$ 是边数。

经典思路：点分治 + 单调队列

这是树上的定长/定区间路径最值问题，常用点分治处理。

点分治步骤

找重心，作为当前根。

计算经过重心的路径。

递归处理子树。

计算经过重心的路径

设重心为 $rt$，对它的每棵子树：

我们维护一个数组 $dp[d]$ 表示从 $rt$ 出发，向下深度为 $d$（边数）的路径的最大点权和。

注意：深度 $d$ 的路径点数为 $d+1$，点权和要包含 $rt$ 的权值。

当我们处理到第 $i$ 棵子树时：

用之前子树的 $dp$ 数组和当前子树的 $dp$ 数组组合，得到经过 $rt$ 的路径。

路径边数 = $d_1 + d_2$，点权和 = $dp_1[d_1] + dp_2[d_2] - v_{rt}$（因为 $rt$ 被算了两遍）。

我们需要对每个可能的 $d_1$，找到 $d_2$ 满足 $L \le d_1 + d_2 \le R$，且 $dp_1[d_1] + dp_2[d_2] - v_{rt}$ 最大。

单调队列优化

对于固定的 $d_1$，$d_2$ 的范围是 $[L-d_1, R-d_1]$。 我们按 $d_1$ 从小到大枚举，$d_2$ 的范围是一个滑动窗口，可以用单调队列求 $dp_2$ 在窗口内的最大值。

更新答案

对于重心 $rt$，我们更新 $f_{rt}$。 对于其他点 $u$，在递归子树时，路径可能完全在子树内，所以需要把信息下传。

算法框架

点分治找重心。

对重心 $rt$：

初始化 $dp[0] = v_{rt}$。

对每棵子树：

计算子树的 $dp$ 数组。

用单调队列结合之前子树的 $dp$ 更新答案。

合并 $dp$ 数组。

清空 $dp$，反向再做一次（因为路径可能从不同方向来）。

递归处理子树，同时把可能的答案下传。

时间复杂度

点分治 $O(n \log n)$

每层单调队列 $O(n)$

总 $O(n \log n)$

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5 + 5; const ll INF = -3472328296227680305LL;

int n, L, R; int v[N]; vector g[N];

bool vis[N]; int sz[N], mx[N], root;

void find_root(int u, int fa, int tot) { sz[u] = 1; mx[u] = 0; for (int v : g[u]) { if (v == fa || vis[v]) continue; find_root(v, u, tot); sz[u] += sz[v]; mx[u] = max(mx[u], sz[v]); } mx[u] = max(mx[u], tot - sz[u]); if (mx[u] < mx[root]) root = u; }

ll dp[N], f[N]; int dep[N]; vector<pair<int, ll>> subtree;

void get_dep(int u, int fa, int d, ll sum) { if (d > R) return; sum += v[u]; dp[d] = max(dp[d], sum); subtree.push_back({d, sum}); for (int v : g[u]) { if (v == fa || vis[v]) continue; get_dep(v, u, d + 1, sum); } }

void solve(int u) { vis[u] = true; // 初始化 vector<vector<pair<int, ll>>> subtrees; for (int v : g[u]) { if (vis[v]) continue; subtree.clear(); get_dep(v, u, 1, 0); // 从u到v算1条边 subtrees.push_back(subtree); } // 合并处理 // 这里省略单调队列合并细节 // 更新 f[u] 和其他点的 f for (int v : g[u]) { if (vis[v]) continue; root = 0; find_root(v, u, sz[v]); solve(root); } }

int main() { cin >> n >> L >> R; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } fill(f + 1, f + n + 1, INF); mx[0] = n; root = 0; find_root(1, 0, n); solve(root); for (int i = 1; i <= n; i++) { cout << f[i] << " \n"[i == n]; } return 0; }

总结

核心是点分治处理经过每个点的路径。

用单调队列求区间最大值来合并子树信息。

注意去重和边界情况。

如果无解输出固定值。