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; vectorint 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 { vectorLine 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); } vectorLine helpHull(vectorLine lines) { vectorLine 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); vectorLine 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; }); // 去重斜率相同保留截距最大的 vectorLine 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 vectorLine 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 节点 ufirst 节点 vx w[u]这是随着查询节点而变的。形如直线 y -z[v] * x z[v] * (z[v] w[v])我们需要在固定节点的固定层数之内查询最大的 y。所以我们会用 w[u] 的离散化值为李超树下标。同时因为你需要很多棵李超树所以需要动态开点。因为题目层数要求 dep[v] - dep[u] ≤ kdep[v] ≤ k dep[u]。所以我们查询时统一到 k dep[u] 再查询这样保证 v 的 dep 合法。时间复杂度当然就是比线段树做法少一个 log 啦。剩下看代码注释#includebits/stdc.h using namespace std; #define int long long const int N 3e5 10; const int inf 1e16; int n, K; vectorint 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要加上的偏移量 }; vectorque 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 值 // 以及每个节点的 depb 值作为一个节点被后续节点查询到的固定偏移量 // 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; }