[COCI 2025/2026 #6] 滑雪 / Skijanje

Hansang1 LV 9 MOD @ 2026-8-26 15:21:45

时隔多天，我来补一下没线段树跑得快的李超树做法。

建议看完下面那篇线段树做法的理论部分再来。

1.介绍

李超树是一种特殊的线段树，专门用来维护"直线集合"，支持：

插入一条直线： $O(logC)$ （ $C$ 是横坐标范围大小）

查询某个 x 的最大值也是 $O(logC)$

指路 b 站的视频李超树基础科普：https://www.bilibili.com/video/BV1hGojBBEJ8

2.分析

本题的外层我们按 dfs 序建立一颗线段树，每个线段树维护区间都是不同子树的组合。

当我们要查询以 t 为头子树内的直线，先固定 t 的子树 dfs 序范围。

查询这个范围内的线段树节点，每个节点都管一颗李超树。

李超树的本质是有一个集合，里面有很多条直线 y = kx + b。

对于 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 啦， $O(Nlog^2N)$ 。

剩下看代码注释：

#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;
}

Hansang1 LV 9 MOD @ 2026-8-20 15:08:33

不知道有没有小馋猫需要树链剖分套线段树套vector维护凸包构式做法。

先放一下：

#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;
}

0
admin LV 10 SU @ 2026-8-12 1:58:56
题意

给出大小为 $n$ 的有根树，边有边权 $z_i,b_i$ 。有向路径 $P$ 的权值为 $f(P)=z_e(z_e+\sum\limits_{i\in P}b_i)+z_s^2$ ，其中 $s,e$ 分别为路径的始边与终边。求所有经过不超过 $k$ 条边的、其上点的深度递增的路径的最大权值。 $1\le k\le n\le3\times10^5$ 。

题解

首先权值在边上不好看，容易转成等价的有点权森林。然后就是求所有自上而下的、点个数不超过 $k$ 的最大路径权值。我们想要化简掉 $\sum$ ，于是我们求出 $S_i$ 表示从根到 $i$ 的所有 $b_i$ 的和，那么 $\sum b_i=S_e-S_{fa(s)}$ 。接下来先给出一个 $\mathcal O(n\log^3 n)$ 的小常数写法，再给出 $\mathcal O(n\log^2 n)$ 的解法。

首先我们考虑按照路径结束点进行分类，即对于 $f(P)=g(s,e)=-z_e\cdot S_{fa(s)}+z_s^2+(z_e^2+z_eS_e)$，固定 $e$ ，求所有 $s$ 的答案。考虑重链剖分，我们希望能够求出一个区间内的 $s$ 的答案，实际上就是求 $\max_s\{-S_{fa(s)}\cdot z_e+z_s^2\}$ 。令 $z_e$ 为变量 $x$ ，那么就是求若干直线在 $x=z_e$ 时的最大值，故显然难度难于凸包类问题。于是我们用线段树维护区间内凸包，即：线段树上每个节点存储这个区间内所有点表示的直线所组成的凸包，容易证明建树的时空复杂度是 $\mathcal O(n\log n)$ 。询问时考虑拆分出来的每一个子区间，都可以在 $\mathcal O(\log n)$ 的时间复杂度内二分求出这个凸包的答案。于是总时间复杂度为 $\mathcal O(n\log^3 n)$ ，由于常数小且很难卡满，所以能过。

另一种做法是，这种带长度限制的树上路径相关问题可以考虑点分治。若我们考虑到某个联通块，此时统计经过重心的路径答案。做有根树问题时，只需要找出重心分出的子树中向原来根方向的那个，从而得到从重心向根的链，那么路径的起点就在这个链上，终点就在其他子树内/重心本身。

依旧固定结束点，那么我们需要的就是链靠近重心的一个前缀所对应的那些直线构成的凸包。于是我们将结束点按照到重心的距离进行分层。从重心向上依次向凸包内加入该点代表的直线，然后询问对应层上所有点的答案。注意有可能某些层没有被询问过，因为这些层比较靠近重心而链的长度较小，需要特殊处理。

接下来考虑如何动态维护凸包。由于加入的直线斜率不一定递增，所以需要用李超线段树维护；由于插入的是直线，所以插入与查询时间复杂度均为 $\mathcal O(\log n)$ 。由点分治的性质，每次处理的联通块大小总和是 $\mathcal O(n\log n)$ 的，所以总时间复杂度为 $\mathcal O(n\log^2 n)$ 。

代码

给出第二种思路的实现：
```
#include<bits/stdc++.h>
#define eps 1e-6
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
#define fi first
#define se second
#define MOD 998244353
#define MAXN 300005
struct LiChao{
	int ls[MAXN],rs[MAXN];
	struct segment{
		LL K,B;
		int p;
		segment(){}
		segment(LL _K,LL _B,int _p){K=_K,B=_B,p=_p;}
		LL operator ()(LL x){return K*x+B;}
	}tr[MAXN*2];
	int idx,rt;
	void clear(){idx=0,rt=0;}
	void Ins(int &k,int l,int r,segment L){
		if(!k){
			k=++idx,tr[k]=L;
			ls[k]=rs[k]=0;
			return;
		}
		int mid=(l+r)>>1;
		if(L(mid)>tr[k](mid))swap(L,tr[k]);
		if(L(l)>tr[k](l))Ins(ls[k],l,mid,L);
		if(L(r)>tr[k](r))Ins(rs[k],mid+1,r,L);
	}
	pair<LL,int> ask(int k,int l,int r,int x){
		if(!k)return make_pair(-INF,0);
		pair<LL,int> res=make_pair(tr[k](x),tr[k].p);
		int mid=(l+r)>>1;
		if(x<=mid)res=max(res,ask(ls[k],l,mid,x));
		else res=max(res,ask(rs[k],mid+1,r,x));
		return res;
	}
}T;
using seg=LiChao::segment;
int n,k,z[MAXN],b[MAXN],fa[MAXN];
LL S[MAXN],ans;
vector<int>G[MAXN],v[MAXN];
void dfs1(int x){
	for(int i:G[x]){
		v[x-1].push_back(i-1),fa[i-1]=x-1;
		if(x-1)v[i-1].push_back(x-1);
		dfs1(i);
	}
}
void dfs2(int x,int fa){
	S[x]=S[fa]+b[x];
	for(int i:v[x])if(i!=fa)dfs2(i,x);
}
int mnmx,cent,siz[MAXN],Siz;
bool bl[MAXN],fl[MAXN];
void getsiz(int x,int fa){
	siz[x]=1,fl[x]=0;
	for(int i:v[x])if(i!=fa&&!bl[i])
		getsiz(i,x),siz[x]+=siz[i];
}
void getcenter(int x,int fa){
	int mx=Siz-siz[x];
	for(int i:v[x])if(i!=fa&&!bl[i])
		mx=max(mx,siz[i]);
	if(mx<mnmx)mnmx=mx,cent=x;
	for(int i:v[x])if(i!=fa&&!bl[i])
		getcenter(i,x);
}
void solve(int x,int blo){
	// Get Center
	mnmx=inf,cent=0;
	getsiz(x,blo),Siz=siz[x];
	getcenter(x,blo);
	// Get Upward-Chain (Down to Up)
	vector<int>chain(1);
	int now=cent;
	while(1){
		chain.push_back(now),fl[now]=1;
		now=fa[now];
		if(!now||bl[now])break;
	}
	// Get BFS layers
	vector<vector<int> >layer(1);
	layer[0].push_back(cent);
	int t;
	for(t=0;t<k;t++){// t->t+1
		if(layer[t].size()==0)break;
		layer.push_back(vector<int>());
		for(int x:layer[t]){
			for(int i:v[x])if(!fl[i]&&!bl[i])
				layer[t+1].push_back(i),fl[i]=1;
		}
	}
	T.clear();
	for(int i=1;i<=k;i++){
		if(i<(int)chain.size()){
			int now=chain[i];
			T.Ins(T.rt,1,100000,seg{-S[fa[now]],1ll*z[now]*z[now],now});
		}else if(layer.size()<=k-i){i=k-layer.size();continue;}
		if(layer.size()<=k-i)continue;
		for(int x:layer[k-i]){
			LL mx=T.ask(T.rt,1,100000,z[x]).fi;
			ans=max(ans,mx+z[x]*(z[x]+S[x]));
		}
	}
	{vector<vector<int> >tem;swap(layer,tem);}
	{vector<int>tem;swap(chain,tem);}
	bl[cent]=1;
	for(int t:v[cent])if(!bl[t])solve(t,cent);
}
signed main(){
	cin>>n>>k;
	vector<int>p_(n+1),z_(n+1),b_(n+1);
	for(int i=2;i<=n;i++)cin>>p_[i],G[p_[i]].push_back(i);
	for(int i=2;i<=n;i++)cin>>z_[i],z[i-1]=z_[i];
	for(int i=2;i<=n;i++)cin>>b_[i],b[i-1]=b_[i];
	dfs1(1),n--,dfs2(0,0);
	for(int i:v[0])solve(i,0);
	cout<<ans;
	
	return 0;
}
```

ID

12642

时间

1000ms

内存

512MiB

难度

标签

省选/NOI−

递交数

已通过

上传者

admin

3 条题解

1.介绍

2.分析

题意

题解

代码

信息

状态

开发

支持

关于

3 条题解

​1.介绍

2.分析

题意

题解

代码

[COCI 2025/2026 #6] 滑雪 / Skijanje

信息

状态

开发

支持

关于

还没有账户？

登录

1.介绍