题目

给一棵第 $i$ 条边边权为 $d_i$ 的有根树，$1$ 为根。对于每个点 $x$，对于满足如下条件的序列 { s 1 , ⋯   , s k } {s_1,cdots,s_k} {s1​,⋯,sk​}：

1. $s_i-1$ 是 $s_i$ 的祖先，且 $s_{i-1}\ne s_i$。
2. $s_1=x$ 中。

求 ${\sum }_{i=2}^k(a_{s_{i-1}}-\text{dist}(s_{i-1},s_i))b_{s_i}$ 的最大值。

$1\le n\le 10^6,0\le a_i,b_i,d_i\le 10^9$，从 $1$ 出发到每个点的距离不超过 $10^9$，最终答案不超过 $2\times 10^{17}$。

分析

考虑朴素的 DP：$$d{p}_u=\underset{v\in \text{subtree of }u}{\max }d{p}_v+(a_u-\text{dist}(u,v))b_v$$ 把 $\text{dist}$ 用深度表示可以得到 $$\begin{array}{rl}d{p}_u=& \underset{v\in \text{subtree of }u}{\max }(d{p}_v+a_u{b}_v+{\text{dep}}_u{b}_v-{\text{dep}}_v{b}_v)\\ =& \underset{v\in \text{subtree of }u}{\max }((a_u+{\text{dep}}_u)b_v+d{p}_v-{\text{dep}}_v{b}_v)\end{array}$$ 设函数 $f_u(x)=b_{u}x+d{p}_u-{\text{dep}}_u{b}_u$，上式转化为 $$d{p}_u=\underset{v\in \text{subtree of }u}{\max }{f}_v(a_u+{\text{dep}}_u)$$ 由于 $f_u(x)$ 是一次函数，很容易想到用李超树维护。一开始想的是用 DFN 序转为区间查询，然后发现李超树不能可持久化（求的是最大值，没有可减性），后来发现只需要合并所有子树，再插入当前点对应的直线，就能得到当前点的李超树了，写动态开点李超树，合并两个树 $u,v$ 方法类似于权值线段树：把 $v$ 的每个直线插入进 $u$。时间复杂度感觉是 $O(n{\log }^{2}n)$ 的，然而题解似乎说是 $O(n\log n)$ 的，没看懂：

不管了反正加个按秩合并跑的飞快……

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

namespace IO { // 板子是 down 里面发的
	const int sz = 1 << 22;
	char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
	inline char gc() {
		return p1 == p2 ? (p2 = (p1 = a) + fread(a, 1, sz, stdin), p1 == p2 ? EOF : *p1++) : *p1++;
	}
	template <class T>
	T Read() {
		T x = 0;
		char c = gc();
		for (; c < '0' || c > '9'; c = gc())
			;
		for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
		return x;
	}
	inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
	inline void pc(char x) {
		*t++ = x;
		if (t - b == sz)
			flush();
	}
	template <class T>
	void Print(T x, char c = 'n') {
		if (x == 0)
			pc('0');
		int t = 0;
		for (; x; x /= 10) p[++t] = x % 10 + '0';
		for (; t; --t) pc(p[t]);
		pc(c);
	}
	struct F {
		~F() { flush(); }
	} f;
}

using IO::Print;
using IO::Read;

typedef long long LL;

const int MAXN = 1000000;
const LL INF = 1ll << 58;

int N, A[MAXN + 5], B[MAXN + 5];

struct Edge {
    int v, w;
    Edge *nxt;
} E[2 * MAXN + 5], *Adj[MAXN + 5], *EdgeCnt = E;

void AddEdge(const int &u, const int &v, const int &w) {
    (++EdgeCnt)->v = v, EdgeCnt->w = w, EdgeCnt->nxt = Adj[u], Adj[u] = EdgeCnt;
}

int Dep[MAXN + 5];

struct Line {
    int k;
    LL b;

    Line() {}
    Line(const int _k, const LL &_b) { k = _k, b = _b; }
    inline LL Cal(const int &x) const { return (LL)k * x + b; }
} L[MAXN + 5];

struct LiChaoTree {
    int NodeCnt;
    struct Node {
        int lch, rch, siz;
        Line l;
    } T[MAXN * 30 + 5];

    void Insert(int &u, const int &lft, const int &rgt, Line cur) {
        if (!u) {
            T[u = ++NodeCnt].l = cur;
            T[u].siz = 1;
            return;
        }
        int mid = ((rgt - lft) >> 1) + lft;
        if (T[u].l.Cal(mid) < cur.Cal(mid))
            std::swap(T[u].l, cur);
        LL lhc = cur.Cal(lft), rhc = cur.Cal(rgt);
        LL lhu = T[u].l.Cal(lft), rhu = T[u].l.Cal(rgt);
        if (lhc <= lhu && rhc <= rhu)
            return;
        if (lhc > lhu)
            Insert(T[u].lch, lft, mid, cur);
        else
            Insert(T[u].rch, mid + 1, rgt, cur);
        T[u].siz = T[T[u].lch].siz + T[T[u].rch].siz;
    }

    int Merge(int u, const int &v, const int &lft, const int &rgt) {
        if (!u || !v)
            return u ^ v;
        Insert(u, lft, rgt, T[v].l);
        int mid = ((rgt - lft) >> 1) + lft;
        T[u].lch = Merge(T[u].lch, T[v].lch, lft, mid);
        T[u].rch = Merge(T[u].rch, T[v].rch, mid + 1, rgt);
        T[u].siz = T[T[u].lch].siz + T[T[u].rch].siz;
        return u;
    }

    LL Query(const int &u, const int &lft, const int &rgt, const int &x) {
        if (!u) return 0;
        if (lft == rgt) {  return T[u].l.Cal(x); }
        LL res = T[u].l.Cal(x);
        int mid = ((rgt - lft) >> 1) + lft;
        if (x <= mid) res = std::max(res, Query(T[u].lch, lft, mid, x));
        else res = std::max(res, Query(T[u].rch, mid + 1, rgt, x));
        return res;
    }
} T;

int DfnCnt;
int Root[MAXN + 5];

LL Dp[MAXN + 5];

void Solve(const int &u, const int &f) {
    for (Edge *i = Adj[u]; i; i = i->nxt) {
        int v = i->v;
        if (v == f)
            continue;
        Dep[v] = Dep[u] + i->w;
        Solve(v, u);
        if (T.T[Root[v]].siz > T.T[Root[u]].siz)
            std::swap(Root[u], Root[v]);
        Root[u] = T.Merge(Root[u], Root[v], 0, 2e9);
    }
    Dp[u] = T.Query(Root[u], 0, 2e9, A[u] + Dep[u]);
    T.Insert(Root[u], 0, 2e9, Line(B[u], -(LL)Dep[u] * B[u] + Dp[u]));
}

int main() {
    N = Read<int>();
    for (int i = 1; i <= N; i++) A[i] = Read<int>(), B[i] = Read<int>();
    for (int i = 1; i < N; i++) {
        int u = Read<int>(), v = Read<int>(), w = Read<int>();
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
    Solve(1, 0);
    for (int i = 1; i <= N; i++) Print(Dp[i]);
    return 0;
}

最后

以上就是殷勤蜜粉为你收集整理的[多校 NOIP 联合模拟 11.30 T4] ZZH 的旅行（李超树合并） | 错题本题目分析代码的全部内容，希望文章能够帮你解决[多校 NOIP 联合模拟 11.30 T4] ZZH 的旅行（李超树合并） | 错题本题目分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。