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

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

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