P15891 [COCI 2025/2026 #6] 滑雪 / Skijanje – 洛谷
借着发烧假把李超树学了。
1.引入 + 线段树做法
孩子们，我们需要在树上找一条长度 ≤ k 的向下路径（从祖先到后代），并最大化紧张度。
设路径为 u → … → v，其中 u 是起点祖先，v 是终点后代。
-
定义 w[x] = 从根到节点 x 的路径速度和（边权 b 的和）
-
则路径速度和 = w[v] – w[u]
-
z_last = z[v]（最后一条边是通向 v 的边）
-
z_first = z[first]，其中 first 是 u 到路径第一个后继节点
也就是为了方便处理，我们把边权下放到点权，放到深度更大的点。
这样到那个点的时候，一定经过这条边。
= z[v] * (z[v] + w[v] – w[u]) + z[first]²
= z[v] * (z[v] + w[v]) – z[v] * w[u] + z[first]²
把 v 看成一条直线：
y = -z[v] * x + z[v]*(z[v] + w[v])
其中 x = w[u]（起点到根的路径速度和）
那么对于固定的起点 u 和第一条边 (u, first)：
-
需要在 first 的子树中找到终点 v
-
最大化 直线_v(w[u]) + z[first]²
-
且要求深度限制：dep[v] – dep[u] ≤ k
这时候做法已经比较明显了，我们可以先树链剖分，再在每一条链上建线段树。
每个线段树节点维护两个系数，分别是直线的 k 和 b。
需要查询时，我们有了可以代入的 x，重新给线段树管的点组排序。
像斜率优化一样排出最优点，取这个最优点。
时间复杂度为枚举点 * 树链剖分 log * 线段树 log * 排序 log。
即 
，在 
的情况下，为 
。
很神秘的复杂度，但是能过，不可思议。
放一个考场代码，非常长，所以不建议学，但是小馋猫们可以看看。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
const LL INF = 4e18;
int n, K;
vector<int> G[N];
int fa[N], dep[N], siz[N], son[N];
int dfn[N], _dfn[N], top[N], tsp;
struct ew {
LL z, b;
} a[N];
LL bsum[N]; // 从根到每个点的 b 前缀和
LL val[N]; // z_i^2
// 树链剖分
void dfs1(int x, int f) {
fa[x] = f;
dep[x] = dep[f] + 1;
siz[x] = 1;
son[x] = 0;
for (int y : G[x]) {
if (y == f) continue;
dfs1(y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}
void dfs2(int x, int tp) {
dfn[x] = ++tsp;
_dfn[tsp] = x;
top[x] = tp;
bsum[x] = bsum[fa[x]] + a[x].b;
val[x] = a[x].z * a[x].z;
if (son[x]) dfs2(son[x], tp);
for (int y : G[x]) {
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
// 线段树维护凸包
#define lc(p) (p << 1)
#define rc(p) ((p << 1) | 1)
struct Line {
LL k, b; // y = k * x + b
};
struct node {
vector<Line> hull;
} tr[N << 2];
// 判断 l2 是否无用（从低到高的下凹凸包）
bool jg(const Line& l1, const Line& l2, const Line& l3) {
// l1.k < l2.k < l3.k
// 若 (b2-b1)/(k1-k2) >= (b3-b2)/(k2-k3)，则 l2 无用
return (__int128)(l2.b – l1.b) * (l2.k – l3.k) >=
(__int128)(l3.b – l2.b) * (l1.k – l2.k);
}
vector<Line> helpHull(vector<Line>& lines) {
vector<Line> hull;
for (auto& ln : lines) {
while (hull.size() >= 2 && jg(hull[hull.size() – 2], hull.back(), ln))
hull.pop_back();
hull.push_back(ln);
}
return hull;
}
void build(int p, int l, int r) {
if (l == r) {
int t = _dfn[l];
if (t != 1) { // 非根节点才对应一条边
tr[p].hull.push_back({-bsum[fa[t]], val[t]});
}
return;
}
int mid = (l + r) >> 1;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
vector<Line> merged;
merged.reserve(tr[lc(p)].hull.size() + tr[rc(p)].hull.size());
merge(tr[lc(p)].hull.begin(), tr[lc(p)].hull.end(),
tr[rc(p)].hull.begin(), tr[rc(p)].hull.end(),
back_inserter(merged),
[](const Line& a, const Line& b) { return a.k < b.k; });
// 去重（斜率相同保留截距最大的）
vector<Line> uniq;
for (auto& ln : merged) {
if (!uniq.empty() && uniq.back().k == ln.k) {
if (ln.b > uniq.back().b) uniq.back().b = ln.b;
}
else {
uniq.push_back(ln);
}
}
tr[p].hull = helpHull(uniq);
}
LL eval(const Line& ln, LL x) {
return ln.k * x + ln.b;
}
// 找 vector 内和 x 结合最大的 y
LL getMax(const vector<Line>& hull, LL x) {
int l = 0, r = (int)hull.size() – 1;
while (l < r) {
int mid = (l + r) >> 1;
if (eval(hull[mid], x) <= eval(hull[mid + 1], x))
l = mid + 1;
else
r = mid;
}
return eval(hull[l], x);
}
LL query(int p, int l, int r, int ql, int qr, LL x) {
if (ql <= l && r <= qr) {
if (tr[p].hull.empty()) return -INF;
return getMax(tr[p].hull, x);
}
int mid = (l + r) >> 1;
LL res = -INF;
if (ql <= mid) res = max(res, query(lc(p), l, mid, ql, qr, x));
if (qr > mid) res = max(res, query(rc(p), mid + 1, r, ql, qr, x));
return res;
}
// 查询路径上深度不小于 L 的 s
LL query_path(int p, int L, LL x) {
LL res = -INF;
while (top[p] != 1) {
int t = top[p];
if (dep[p] < L) break;
int l = dfn[t], r = dfn[p];
if (dep[t] < L) {
int offset = L – dep[t];
l = dfn[t] + offset;
}
if (l <= r) {
res = max(res, query(1, 1, n, l, r, x));
}
p = fa[t];
}
// 最后一条重链（以根为链头）
if (p != 0 && dep[p] >= L) {
int t = 1;
int l = dfn[t], r = dfn[p];
if (dep[t] < L) {
int offset = L – dep[t];
l = dfn[t] + offset;
}
if (l <= r) {
res = max(res, query(1, 1, n, l, r, x));
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> K;
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
G[p].push_back(i + 1);
}
for (int i = 1; i < n; ++i) cin >> a[i + 1].z;
for (int i = 1; i < n; ++i) cin >> a[i + 1].b;
if (n == 1) {
cout << 0 << '\\n';
return 0;
}
dfs1(1, 0);
tsp = 0;
dfs2(1, 1);
build(1, 1, n);
LL ans = -INF;
for (int x = 2; x <= n; x ++) {
LL z_x = a[x].z;
LL S_x = bsum[x];
// 边数限制
// dep[x] – dep[s] + 1 <= K => dep[s] >= dep[x] – K + 1
int L = max(2, dep[x] – K + 1);
if (L > dep[x]) continue;
LL t = query_path(x, L, z_x);
if (t == -INF) continue;
LL sum = t + z_x * z_x + z_x * S_x;
ans = max(ans, sum);
}
cout << ans << "\\n";
return 0;
}
2.正解李超树
有小朋友要说：我也妹学过李超树呀，肿么办？
没事呀我也才是刚学。
只要你学过线段树，我就有信心教会你。
李超树是一种特殊的线段树，专门用来维护"直线集合"，支持：
-
插入一条直线：
（C 是横坐标范围大小） -
查询某个 x 的最大值也是
指路 b 站的视频李超树基础科普：https://www.bilibili.com/video/BV1hGojBBEJ8
本题的外层我们按 dfs 序建立一颗线段树，每个线段树维护区间都是不同子树的组合。
当我们要查询以 t 为头子树内的直线，先固定 t 的子树 dfs 序范围。
查询这个范围内的线段树节点，每个节点都管一颗李超树。
李超树的本质是有一个集合，里面有很多条直线 y = kx + b。
支持两个操作：
1.插入一条新直线。
2.查询在 x = X 时，所有直线中 y 的最大值。
对于 last 节点 u，first 节点 v，x = w[u]，这是随着查询节点而变的。
形如直线 y = -z[v] * x + z[v] * (z[v] + w[v])，我们需要在固定节点的固定层数之内查询最大的 y。
所以我们会用 w[u] 的离散化值为李超树下标。
同时因为你需要很多棵李超树，所以需要动态开点。
因为题目层数要求 dep[v] – dep[u] ≤ k，dep[v] ≤ k + dep[u]。
所以我们查询时统一到 k + dep[u] 再查询，这样保证 v 的 dep 合法。
时间复杂度当然就是比线段树做法少一个 log 啦，
。
剩下看代码注释：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
const int inf = 1e16;
int n, K;
vector<int> G[N], up[N << 1];
int fa[N], w[N], z[N], W[N], c, b[N];
int dfn[N], dep[N], tsp, rig[N];
int rt[N << 2]; // 外层线段树每个节点对应的李超树根节点编号
struct que {
int l, r, x, pl;
// 查询区间 [l,r]（dfs序），x：横坐标（路径速度和的离散化排名），pl：要加上的偏移量
};
vector<que> q[N << 1];
struct node{
int ls, rs; // 左右儿子
int h; // 当前节点存储的优势直线编号（节点编号）
} tr[N << 4];
int tot;
int get_slo(int i, int x){
return -W[x] * z[i] + b[i];
}
// 插入直线 h 到李超树的节点 id，区间为 [l, r]（离散化后的排名区间）
void insert(int &p, int l, int r, int h) {
int mid = (l + r) >> 1;
if(!p) p = ++ tot; // 创建新节点
// 如果新直线在中点处更优，则交换，让当前节点保留较优直线
if(get_slo(h, mid) > get_slo(tr[p].h, mid)) swap(tr[p].h, h);
// 如果新直线在左端点更优，则递归插入左子树
if(get_slo(h, l) > get_slo(tr[p].h, l)) insert(tr[p].ls, l, mid, h);
// 如果新直线在右端点更优，则递归插入右子树
if(get_slo(h, r) > get_slo(tr[p].h, r)) insert(tr[p].rs, mid + 1, r, h);
}
// 查询李超树在横坐标 x（离散化排名）处的最大值
int findrk(int p, int l, int r, int x) {
if(!p) return -inf;
int mid = (l + r) >> 1;
int res = get_slo(tr[p].h, x); // 当前节点优势直线在 x 处的值
if(l == r) return res;
// 继续向下查询，取路径上所有直线值的最大值
return max( x <= mid ? findrk(tr[p].ls, l, mid, x)
: findrk(tr[p].rs, mid + 1, r, x), res);
}
// 单点更新：在 dfs 序位置 x 插入直线 h
void change(int p, int l, int r, int x, int h) {
insert(rt[p], 1, c, h); // 将直线 h 插入到当前线段树节点对应的李超树中
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) change(p << 1, l, mid, x, h);
else change((p << 1) | 1, mid + 1, r, x, h);
}
// 区间查询：在 dfs 序区间 [x, y] 内，查询横坐标为 X 时的最大值
int query(int p, int l, int r, int x, int y, int X) {
if(x <= l && y >= r) return findrk(rt[p], 1, c, X); // 完全覆盖，直接查询该节点的李超树
int mid = (l + r) >> 1;
int res = -inf;
if(x <= mid) res = query(p << 1, l, mid, x, y, X);
if(y > mid) res = max(res, query((p << 1) | 1, mid + 1, r, x, y, X));
return res;
}
// 在第一个 dfs 里，我们需要搞定 dfs 序和路径前缀和 w 值
// 以及每个节点的 dep，b 值作为一个节点被后续节点查询到的固定偏移量
// rig 则是该子树结束点的 dfs 序
void dfsa(int x) {
dfn[x] = ++ tsp;
for (int y : G[x]) {
dep[y] = dep[x] + 1;
w[y] += w[x];
dfsa(y);
}
rig[x] = tsp;
b[x] = z[x] * (z[x] + w[x]);
}
// 在第二个 dfs 序里，up 存的是当前层数可以被插入的节点
// q 则是在当前层数可以被查询的节点
void dfsb(int x) {
up[dep[x]].push_back(x);
for (int y : G[x]) {
q[K + dep[x]].push_back({dfn[y], rig[y], w[x], z[y] * z[y]});
// 这里的 pl 相当于 z[last] * z[last]，是更随查询点的固定量
dfsb(y);
}
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> K;
z[0] = 0; // 进行一个没什么用的初始化动作
b[0] = -inf;
w[1] = 0;
for (int i = 2; i <= n; i ++) {
int x;
cin >> x;
fa[i] = x;
G[x].push_back(i);
}
for (int i = 2; i <= n; i ++) {
cin >> z[i];
}
for (int i = 2; i <= n; i ++) {
cin >> w[i];
}
tsp = 0;
dfsa(1);
for (int i = 1; i <= n; i ++) {
W[i] = w[i];
}
sort(W + 1, W + n + 1);
c = unique(W + 1, W + n + 1) – W – 1;
for (int i = 1; i <= n; i ++) {
w[i] = lower_bound(W + 1, W + c + 1, w[i]) – W;
}
dfsb(1);
tot = 0;
int ans = 0;
for (int i = 1; i <= (n << 1); i ++) {
for (int j : up[i]) { // 将深度为 i 的所有节点作为直线插入（这些节点可以作为终点）
change(1, 1, n, dfn[j], j); // 按 dfs 序单点插入直线 j
}
for (auto j : q[i]) {
ans = max(ans, query(1, 1, n, j.l, j.r, j.x) + j.pl);
}
}
cout << ans << "\\n";
return 0;
}
