题目描述

1. 商路
   AI大赛

C++ 代码

#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1e18;
const int N = 1e5 + 5;

// 边结构体：存储目的节点 t，边权 s，以及下一条边的下标 ne
struct Edge
{
    int t, s, ne;
} e[N];

int h[N], idx1; // 邻接表头数组 h 和边计数器 idx1

// 添加边到邻接表
void add(int u, int v, int s) {
    e[++idx1] = {v, s, h[u]}; // 新增一条边，指向 v，权重为 s
    h[u] = idx1; // 更新节点 u 的头指针
}

ll v[N], f[N]; // 节点的价值 v 和期望路径长度 f
ll d[N], dp[N]; // 节点到根的距离 d 和 dp 值
int sz[N], ind[N], idx2; // 子树大小 sz，节点的深度优先序 ind，DFS 序计数器 idx2

// 第一趟 DFS：计算子树大小、DFS 序和节点到根的距离
void dfs1(int from, ll s)
{
    ind[from] = ++idx2; // 给节点分配 DFS 序
    d[idx2] = s; // 记录节点到根的距离
    sz[from] = 1; // 初始化子树大小为 1
    for (int i = h[from]; i; i = e[i].ne) // 遍历邻接表
        dfs1(e[i].t, s + e[i].s), sz[from] += sz[e[i].t]; // 递归访问子节点并累加子树大小
}

#define sq(x) ((x) * (x))            // 计算平方，宏定义确保加括号避免运算优先级问题
#define ff(x) (dp[x] - sq(d[x]))     // 凸包点的纵坐标值，即 dp[x] - d[x]^2
#define dy(x1, x2) (ff(x1) - ff(x2)) // 计算纵坐标差
#define dx(x1, x2) (d[x1] - d[x2])   // 计算横坐标差

// 凸包节点
struct Node
{
    bool vis; // 是否已构造凸包
    vector<int> q; // 存储凸包的节点序号

    // 构造凸包
    void build()
    {
        vector<int> temp; // 临时存储构造的凸包
        for (int i : q) {
            while (temp.size() > 1) {
                int t1 = temp[temp.size() - 2], t2 = temp.back();
                // 判断新点是否应加入凸包
                if ((d[t2] - d[t1]) * (dp[i] - dp[t2]) >= (d[i] - d[t2]) * (dp[t2] - dp[t1])) {
                    temp.pop_back(); // 去除无用点
                } else {
                    break;
                }
            }
            temp.push_back(i); // 添加新点到凸包
        }
        q.swap(temp); // 更新凸包
        vis = true; // 标记凸包已构造
    }

    // 查询凸包上斜率最大值对应的点
    ll find(int i)
    {
        if (!vis) build(); // 如果凸包未构造，先构造

        ll k = -2 * (f[i] + d[ind[i]]); // 查询点的斜率
        int l = 0, r = q.size() - 1;   // 二分范围
        while (l < r) {
            int mid = (l + r) / 2;
            // 判断是否需要向左收缩范围
            if ((dp[q[mid + 1]] - dp[q[mid]]) <= k * (d[q[mid + 1]] - d[q[mid]])) {
                r = mid; // 更新右边界
            } else {
                l = mid + 1; // 更新左边界
            }
        }
        return dp[q[l]] + v[i] - sq(f[i] + d[ind[i]] - d[q[l]]); // 返回最优值
    }
} tr[N << 2];

#define cur tr[x]          // 当前线段树节点
#define lch tr[x << 1]     // 左子节点
#define rch tr[x << 1 | 1] // 右子节点
#define mid (l + r >> 1)   // 中间位置

// 归并两个子节点的凸包
void merge(int x)
{
    cur.q.resize(lch.q.size() + rch.q.size()); // 预分配大小
    int i = 0, j = 0, k = 0;
    while (i < lch.q.size() || j < rch.q.size()) {
        if (i == lch.q.size()) {
            cur.q[k++] = rch.q[j++];
        } else if (j == rch.q.size()) {
            cur.q[k++] = lch.q[i++];
        } else if (d[lch.q[i]] <= d[rch.q[j]]) {
            cur.q[k++] = lch.q[i++];
        } else {
            cur.q[k++] = rch.q[j++];
        }
    }
}

// 构造线段树
void build(int x, int l, int r)
{
    cur.vis = false; // 初始化未构造凸包
    if (l == r) {
        cur.q.resize(1, l); // 叶节点存储单点
    } else {
        build(x << 1, l, mid); // 递归构造左子树
        build(x << 1 | 1, mid + 1, r); // 递归构造右子树
        merge(x); // 合并子树结果
    }
}

int L, R, n, T; // L 和 R 为当前查询的区间

// 在线段树上查询
ll query(int x, int l, int r, int i)
{
    if (l >= L && r <= R) {
        return cur.find(i); // 当前区间完全包含查询区间，直接查询
    } else {
        ll res = 0;
        if (mid >= L) res = max(res, query(x << 1, l, mid, i)); // 查询左子树
        if (mid < R) res = max(res, query(x << 1 | 1, mid + 1, r, i)); // 查询右子树
        return res;
    }
}

// 第二趟 DFS：计算 dp 值
void dfs2(int from)
{
    if (!h[from]) return; // 如果没有子节点直接返回
    for (int i = h[from]; i; i = e[i].ne) {
        dfs2(e[i].t); // 递归处理子节点
    }
    L = ind[from] + 1; // 查询范围的左端点
    R = ind[from] + sz[from] - 1; // 查询范围的右端点
    dp[ind[from]] = query(1, 1, n, from); // 查询最优值并更新 dp
}

int main()
{
    scanf("%d", &T); // 输入测试用例数量
    while (T--) {
        idx1 = idx2 = 0; // 重置边计数器和 DFS 序计数器
        scanf("%d", &n); // 输入节点数量
        for (int i = 1, u, s; i <= n; i++) {
            scanf("%d%d%lld%lld", &u, &s, v + i, f + i); // 输入边和节点数据
            add(u, i, s); // 添加边
        }
        dfs1(1, 0); // 第一次 DFS，计算基本信息
        build(1, 1, n); // 构造线段树
        dfs2(1); // 第二次 DFS，计算 dp 值

        ll ans = 0; // 计算总答案
        for (int i = 1; i <= n; i++) {
            ans = (ans + dp[i]) % mod; // 累加 dp 值
            dp[i] = 0; // 重置 dp 值
        }
        printf("%lld\n", ans); // 输出结果
    }
    return 0;
}