UOJ #284. 快乐游戏鸡题解（长链剖分+单调栈合并）
题面
一番战斗之后，程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下：“追！”，于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创，出掉这一年的恶气。
可是程序猿一追就走，一走就跑，一跑就无影无踪。计算鸡们开始跋山涉水寻找程序猿的踪迹。快乐游戏鸡跟随大部队走着走着，突然说道：“我好像打过类似的游戏”。
快乐游戏鸡玩过的游戏是这样的：给定一棵 \(n\) 个结点的树，其中 \(1\) 号结点是根。每次玩家可以在树上行走，走过一条边需要 \(1\) 秒的时间，但只能往当前所在的点的某个儿子走，不能往父亲走。每次游戏需要从 \(s\) 号结点走到 \(t\) 号结点去。
玩家有一个总死亡次数，初始为 \(0\)。每个结点上有一个程序猿和一个参数 \(w_i\)，如果走到结点 \(i\) 的时候，当前总的死亡次数小于 \(w_i\)，那么玩家就会立刻死亡并回到起点 \(s\)，且该死亡过程不需要时间；如果总死亡次数大于等于 \(w_i\)，那么玩家就能熟练地对付程序猿从而安然无恙。注意每次游戏时不需要考虑 \(s\) 和 \(t\) 上的程序猿。
该游戏会进行若干轮，每轮会清空总死亡次数并给出一组新的 \(s, t\)。现在请你对于每一轮游戏输出走到 \(t\) 所需要的最短时间（单位为秒）。
保证每个询问的 \(s\) 可以到达 \(t\)。
数据范围
\(1 \le n, q \le 3e5,\quad 1 \le w \le 1e9\)
Solution
本题作如下假设
- \(Hint1\) 考虑单条路径，则有我们在\(path\)上会受到阻碍当且仅当满足如下条件，那么对于这一条路径来说，我们想要维护这个信息是可以用单调栈维护的，只要满足以上条件，那就可以把这个点放入\(stk\)。
-
\(Hint2\) 考虑\(s\)为\(root\)的子树，那就会有多条由子树出发到叶子节点的\(path\)，那我们可以发现，如果有一个点\(p\in subtree(s) \&\& p\notin path(s\rightarrow t)\)，但是\(stk[i].w < p.w\&\&stk[i + 1].dep > p.dep\)，那么此时，这个点也是可以放入\(stk\)的，所以我们要维护的单调栈应该是
\[subtree[i].dep < subtree[j].dep \quad \&\&\quad subtree[i].w < subtree[j].w\quad (i < j) \] -
\(Hint3\) 考虑如何维护这个\(stk\)，如果我们每次到一个点\(u\)，然后直接\(dfs\)子树获取所有点并尝试放入\(stk\)的话，虽然能够维护，但是复杂度不对。考虑\(dfs\)的过程，如果我们能在搜到一个叶子节点的时候，把当前的\(stk\)存下来，如果回溯到子树根节点时，再把这些\(stk\)合并起来，那么如果我们合并方式合理，那就可以优化复杂度，比如用启发式合并可以做到\(O(n\log{n})\)，又由于这个栈是可以以\(dep\)为主关键字的，所以可以用长链剖分，再在回溯的过程进行合并，就能做到\(O(n)\)（还没想通复杂度为什么是\(O(n)\)）.
-
\(Hint4\) 考虑统计答案
\[sum = \sum{(w[i] - w[i - 1])*dep[i]}(i \in path(s\rightarrow t)) \]
但我们现在是在一个某一个节点上，当前的\(stk\)中存的是由子树中的节点所构成的，但是\(t\)不一定在 这个\(stk\)中，所以我们需要用一个二分找到当前\(stk\)中第一个\(w \ge max(path(s\rightarrow t).w)\)，我们令 它为\(pos\)， 但是如果我们一个一个去求和那么时间复杂度又变得不可接 受，这里我们可以用一个 前缀和或者后缀和来维护这个信息，由于我们使用的是栈，由于先入后出的性质我们只能记后缀 和，这样子每次从栈顶拿出元素，后面的和就不会受到影响。
-
\(Hint5\) 考虑求解\(w \ge max(path(s\rightarrow t).w)\)，我们直接用树上倍增的方式即可求解
-
\(Hint6\) 关于栈的空间分配问题，由于每个子树下的栈的空间最大都会达到\(dep\)，如果每个都去开一个数组显然空间复杂度会达到\(O(n^2)\)，考虑空间复用。在长链剖分自下往上的回溯过程中，已经被并入长链的轻链是不会再用到的，并且长链上父节点是可以直接继承重儿子的信息的，所以我们只要按照长链剖分的\(dfn\)序来进行空间复用就行，我们对每一个节点\(p\)可以开一对\(L[p]（栈顶）, R[p]（栈底）\)表示当前节点\(stk\)的起始位置和结束位置，优先遍历重儿子，因为单调栈长度最大为\(dep[p]\)，而\(dfn[p]\ge dep[p]\)所以肯定是空间够用的。
-
\(Hint7\) 计算答案时还有很多细节，加在代码的注释中。
Code
int n;
vector<int> e[maxn];
int son[maxn], h[maxn], dep[maxn], in[maxn], idx;
ll w[maxn];
int par[maxn][20], mxw[maxn][20];
void dfs(int u, int p) {
par[u][0] = p;
mxw[u][0] = w[par[u][0]];//倍增初始化，从父亲开始算即可，因为不算终点
for (int i = 1; i < 20; ++i) {
par[u][i] = par[par[u][i - 1]][i - 1];
mxw[u][i] = max(mxw[u][i - 1], mxw[par[u][i - 1]][i - 1]);
}
h[u] = 1;
dep[u] = dep[p] + 1;
for (auto v : e[u]) {
dfs(v, u);
h[u] = max(h[u], h[v] + 1);//长链剖分
if (!son[u] || h[v] > h[son[u]]) son[u] = v;
}
}
vector<pii> qr[maxn];//离线询问
ll Ans[maxn];
struct node {
ll w, d;
node() : w(0), d(0) {}
node (int _w, int _d) : w(_w), d(_d) { }
} stk[maxn], que[maxn];//一个队列用来辅助单调栈合并
int L[maxn], R[maxn], top;
ll pre[maxn];
void insert(int u, node p) {//单个节点的插入(保证dep小于栈顶，因为合并是一个自底向上的过程，插入的点一定比当前栈中的深度小)
while (L[u] <= R[u] && p.w >= stk[L[u]].w) L[u]++;//dep小且dep大的肯定更优
if (L[u] > R[u]) {//特判为空的情况
L[u]--;
pre[L[u]] = 0;
stk[L[u]] = p;
} else {
if (p.d < stk[L[u]].d) {
stk[--L[u]] = p;
pre[L[u]] = pre[L[u] + 1] + stk[L[u] + 1].d * (stk[L[u] + 1].w - stk[L[u]].w);//这里少加了自身死亡次数*下一个点的深度，因为不算起点
}
}
}
void merge(int u, int v) {
top = 0;
while (L[u] <= R[u] && stk[L[u]].d <= stk[R[v]].d) que[++top] = stk[L[u]++];//先把深度小的暂存
while (top && L[v] <= R[v]) {
if (que[top].d >= stk[R[v]].d) {
insert(u, que[top--]);
} else {
insert(u, stk[R[v]--]);
}
}
while (top) insert(u, que[top--]);
while (L[v] <= R[v]) insert(u, stk[R[v]--]);
}
int getmxw(int u, int v) {
int ans = 0;
for (int i = 19; i >= 0; --i) {
if (dep[par[v][i]] > dep[u]) {
ans = max(ans, mxw[v][i]);
v = par[v][i];
}
}
return ans;
}
ll calc(int u, int v) {//计算答案
int mx = getmxw(u, v);
int l = L[u], r = R[u];
int pos = L[u];
while (l <= r) {//二分到单调栈中第一个w>=mx的点
int mid = l + r >> 1;
if (stk[mid].w >= mx) {
pos = mid;
r = mid - 1;
} else l = mid + 1;
}
if (stk[L[u]].w >= mx) {//如果开头就比mx大
return mx * (stk[L[u]].d - dep[u]);
} else {//要减掉多余的
return pre[L[u]] - pre[pos] + stk[L[u]].w * stk[L[u]].d - (stk[pos].w - mx) * stk[pos].d - 1ll * dep[u] * mx;
}
}
void DFS(int u) {
in[u] = ++idx;
if (son[u]) {
DFS(son[u]);
L[u] = L[son[u]]; R[u] = R[son[u]];
} else {
L[u] = idx, R[u] = idx - 1;
}
for (int v : e[u]) {
if (v != son[u]) {
DFS(v);
merge(u, v);
}
}
for (auto i : qr[u]) {
auto [v, id] = i;
Ans[id] = calc(u, v) + dep[v] - dep[u];
}
insert(u, node(w[u], dep[u]));
}
void solve(int cas) {
int n; cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
}
for (int i = 2; i <= n; ++i) {
int u; cin >> u;
e[u].eb(i);
}
dep[0] = -1;
dfs(1, 0);
int q; cin >> q;
for (int i = 1; i <= q; ++i) {
int s, t; cin >> s >> t;
qr[s].eb(t, i);
}
DFS(1);
for (int i = 1; i <= q; ++i) {
cout << Ans[i] << '\n';
}
}