标签：线段 SZ 城市 到达 购票 NOI2014 P2305 李超树

P2305 [NOI2014] 购票

题意

今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 \(n\) 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。

全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 \(n\) 个城市用 \(1\sim n\) 的整数编号。其中 SZ 市的编号为 \(1\)。对于除 SZ 市之外的任意一个城市 \(v\)，我们给出了它在这棵树上的父亲城市 \(f_v\) 以及到父亲城市道路的长度 \(s_v\)。

从城市 \(v\) 前往 SZ 市的方法为：选择城市 \(v\) 的一个祖先 \(a\)，支付购票的费用，乘坐交通工具到达 \(a\)。再选择城市 \(a\) 的一个祖先 \(b\)，支付费用并到达 \(b\)。以此类推，直至到达 SZ 市。

对于任意一个城市 \(v\)，我们会给出一个交通工具的距离限制 \(l_v\)。对于城市 \(v\) 的祖先 A，只有当它们之间所有道路的总长度不超过 \(l_v\) 时，从城市 \(v\) 才可以通过一次购票到达城市 A，否则不能通过一次购票到达。

对于每个城市 \(v\)，我们还会给出两个非负整数 \(p_v,q_v\) 作为票价参数。若城市 \(v\) 到城市 A 所有道路的总长度为 \(d\)，那么从城市 \(v\) 到城市 A 购买的票价为 \(dp_v+q_v\)。

每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。

题解

模拟赛的时候脑子爆掉了。
设 \(f_i\) 表示 \(i\) 号点到根的最小花费。 显然有转移方程：

\[f_i = \min (f_j+(d_i-d_j)p_i+q_i) \]

这里满足 \(j\) 是 \(i\) 的祖先，\(d_i-d_j \leq l_i\)
看着很斜优，改一下：

\[f_i = min(-d_jp_i+f_j)+d_ip_i+q_i \]

显然对于一条一次函数 \(y = kx+b\)，\(x = p_i\) ， \(k = -d_j\) ，\(b = f_j\)，可以用李超树维护。

若果是一条链的话已经可以直接做了，但是有树的情况，并且还有一个转移距离的限制。

1.如果是树的情况，我们其实可以撤销李超树，退出一个点的时候在树上删除对应直线就好了。

2.如果在链上有距离限制怎么做，显然我们是要查的是一段区间中的李超树的情况，使用线段树套李超树，用类似于标记永久化的方式，对线段树上的每一个节点都维护一颗李超树，插入一条线段的时候吧这个位置在线段树的路径上的李超树都插入就好了。

3.如果距离限制和树拼起来改怎么做，显然可以套一个树剖上去将树上问题序列化去做到 \(O(nlog^3n)\)，出栈序是一个不错的选择，对于一个点 \(i\) ，在出栈序里面找到第一个满足 \(d_i-d_j \leq l_i\) 的点，出栈序中 \(i,j\) 之间有贡献的点都是 \(i,j\) 的路径之上的，不是的都还没有做到，没有贡献，最后时间复杂度 \(O(nlog^2n)\)。

...

这道题是一道技巧性很强的一道题，出栈序对于实时算贡献并且是路径上的问题可能是一个比较好的选择。

标签：线段,SZ,城市,到达,购票,NOI2014,P2305,李超树
From： https://www.cnblogs.com/snow-panther/p/17504445.html