P2305 [NOI2014] 购票
Solution
记 \(f_{i}\) 表示 \(i\) 节点处的答案。\(f_1 = 0\)。记 \(d_i\) 表示根节点到点 \(i\) 的距离，容易得到 \(O(n^2)\) 的 dp 转移：
\[f_{i} \xleftarrow{\min} f_j + (d_i - d_j)\times p_i + q_i, d_i - d_j \le l_i \]设 \(y = f_i - d_i \times p_i - q_i, slope = -d_j, x = p_i, b = f_j\)，这是一个斜率优化的形式。
但我们更应该注意，\(y = slope\times x + b\) 的一次函数形式可以用李超线段树维护，并且容易在树上实现撤销。
麻烦在于有 \(d_i - d_j \le l_i\) 的限制，那么需要实现任意一条链上的线段并的信息查询。
首先考虑序列上的区间查询，可以采用 线段树套李超线段树，外层线段树的叶节点存每个位置的一条线段，外层线段树上的一个节点将其子树内包含的所有线段并起来。这个过程并不用真的进行 pushup，而是对每一条线段直接插到外层线段树上的 \(\log\) 个节点（的李超线段树）上去。
然后考虑树上的区间查询。一种 naive 的想法是树链剖分，做到时间复杂度 \(O(n\log^3{n})\)，空间复杂度 \(O(n\log{n})\)（考虑线段总数为 \(O(n)\)，每条线段至多插入 \(O(\log{n})\) 次，由于李超线段树的特性——信息并不一定要保存在叶节点，因此遇到空节点就会立即 return，也就是说，插入一条线段最多导致动态开出 \(1\) 个点，所以外层线段树上所有节点的李超线段树的节点总数是 \(O(n\log{n})\) 的）。
优化：将外层线段树上的叶节点对应的下标定义为原树上节点的 出栈序（最后一次被遍历到的时间顺序）。在 dfs 的过程中，记 \(ord_i\) 表示点 \(i\) 的出栈序，若能更新一个点 \(u\) 的最远点为 \(v\)，则外层线段树上区间查询 \(ord_u\) 到 \(ord_v\) 即可得到 \(u \to v\) 的链上所有线段并的结果。可以这样做的正确性保证在于，\(ord_u \sim ord_v\) 中对应两类点，一类是 \(u \to v\) 链上的点，另一类是不在链上的点，而后者此时一定未被遍历，信息未被上传，因此在 \(ord_u \sim ord_v\) 内的查询是十分精确的。
该做法的时间复杂度为 \(O(n\log^2{n})\)，空间复杂度仍为 \(O(n\log{n})\)。
总结一下此题给我印象极深的两点：
-
“线段并” 这个一眼李超线段树合并的东西，通过外层套上一棵线段树，将多条线段的 “合并” 转化为每条线段的 “插入”。
在外层线段树上维护线段并，本质上与李超线段树合并擅长维护的 “子树信息合并到父节点” 的问题（如 CF932F Escape Through Leaf）本质相同。但在这里，初始时所有线段都处于叶节点处。在我们构建出的深度为 \(O(\log{n})\) 的外层线段树中，暴力将一条线段插入到包含它的所有节点中，时间复杂度是正确的（\(O(n\log^2{n})\)），因此没有必要进行李超线段树合并；而对于普通的李超线段树合并问题，每个节点都会挂一条线段，并且树的深度无法保证，所以就不能暴力考虑分别插入每条线段，否则时间复杂度会退化成 \(O(n^2\log{n})\)，甚至不如暴力。
-
树上链查询的问题可以考虑 出栈序。看似多考虑了节点信息，实则并没有真正查询到这些信息。
一对时间戳在岔路间流动着。我的时间戳站在谷底接受漫天星火的审判。审判之下，岁月的鸿沟被过往湮灭于黑暗，那里是我将要驻足的地方。
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define lowbit(x) x & (-x)
#define PII pair<int, int>
#define PLI pair<LL, int>
#define MP make_pair
#define VI vector<int>
#define VII vector<int>::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define SI set<int>
#define SII set<int>::iterator
#define QI queue<int>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
int inc(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
Sqr(x), k >>= 1;
}
return res;
}
const int N = 2e5 + 5;
const int M = 3e7 + 5;
const int Range = 1e6 + 5;
const LL INF = 1e18;
int n, typ;
struct Line
{
LL k, b;
}line[N];
LL F(int id, int x)
{
return 1LL * line[id].k * x + line[id].b;
}
struct LiChaoSGT
{
int dop;
struct SegTree
{
int ls, rs;
int id;
}tr[M];
void make_new(int &p, int id)
{
p = ++dop;
tr[p].id = id;
}
void insert(int &p, int l, int r, int id)
{
if(!p) return (void)make_new(p, id);
int mid = l + (r - l) / 2;
if(F(id, mid) < F(tr[p].id, mid)) swap(id, tr[p].id);
if(F(id, l) >= F(tr[p].id, l) && F(id, r) >= F(tr[p].id, r)) return;
if(F(id, l) < F(tr[p].id, l)) insert(tr[p].ls, l, mid, id);
else insert(tr[p].rs, mid + 1, r, id);
}
LL query(int p, int l, int r, int x)
{
if(!p) return INF;
int mid = l + (r - l) / 2;
LL res = F(tr[p].id, x);
if(mid >= x) chkmn(res, query(tr[p].ls, l, mid, x));
else chkmn(res, query(tr[p].rs, mid + 1, r, x));
return res;
}
}slopeT; // LCT (bushi)
int rt[M];
struct SGT
{
void modify(int p, int l, int r, int x, int id)
{
slopeT.insert(rt[p], 0, Range, id);
if(l == r) return;
int mid = l + (r - l) / 2;
if(mid >= x) modify(ls(p), l, mid, x, id);
else modify(rs(p), mid + 1, r, x, id);
}
LL query(int p, int l, int r, int L, int R, int x)
{
if(l >= L && r <= R)
return slopeT.query(rt[p], 0, Range, x);
int mid = l + (r - l) / 2;
LL res = INF;
if(mid >= L) chkmn(res, query(ls(p), l, mid, L, R, x));
if(mid < R) chkmn(res, query(rs(p), mid + 1, r, L, R, x));
return res;
}
}T;
vector<PLI> G[N];
int p[N];
LL d[N], q[N], l[N], dp[N];
int ord[N], timestamp;
int f[N][21], leapf[N];
LL s[N][21];
void predfs(int u, int fa)
{
for(int i = 1; i < 21; ++i)
{
f[u][i] = f[f[u][i - 1]][i - 1];
s[u][i] = s[u][i - 1] + s[f[u][i - 1]][i - 1];
}
leapf[u] = u;
for(int i = 20; i >= 0; --i)
if(s[leapf[u]][i] <= l[u] && f[leapf[u]][i])
{
l[u] -= s[leapf[u]][i];
leapf[u] = f[leapf[u]][i];
}
for(auto nxt : G[u])
{
int v = nxt.second;
LL w = nxt.first;
if(v == fa)
continue;
f[v][0] = u;
s[v][0] = w;
d[v] = d[u] + w;
predfs(v, u);
}
ord[u] = ++timestamp;
}
void dfs(int u, int fa)
{
line[u] = (Line){-d[u], dp[u]};
T.modify(1, 1, n, ord[u], u);
for(auto nxt : G[u])
{
int v = nxt.second;
if(v == fa)
continue;
dp[v] = T.query(1, 1, n, ord[v], ord[leapf[v]], p[v]) + 1LL * d[v] * p[v] + q[v];
dfs(v, u);
}
}
int main()
{
scanf("%d %d", &n, &typ);
for(int i = 2; i <= n; ++i)
{
int fa; LL w;
scanf("%d %lld %d %lld %lld", &fa, &w, &p[i], &q[i], &l[i]);
G[i].EB(MP(w, fa));
G[fa].EB(MP(w, i));
}
predfs(1, 0);
dfs(1, 0);
for(int i = 2; i <= n; ++i)
printf("%lld\n", dp[i]);
return 0;
}