「UOJ 284」快乐游戏鸡 题解

---

• 题目链接: https://uoj.ac/problem/284

大体是将询问离线, 利用长链剖分维护子树内的单调栈. 还有一火车的细节

解题思路

先考虑在一条链上怎么做.

首先将所有点按 $1$ 到 $n$ 从左到右排布, 此时得到了一个序列. 对于一次询问 $(s, t)$, 从 $s$ 出发走向 $t$ (也只能这样走), 设在这条路径上依次经过节点 $i, j$. 如果有 $w_i \ge w_j$, 那么一定不会在 $j$ 上死亡.

如果我们直接删去这样的 $j$, 那么可以得出一个深度单调递增, 同时 $w$ 严格单调递增的单调栈.

在维护出单调栈后, 如何计算答案呢?

记 $f_u$ 为经过单调栈中上一个位置 $u$ 的花费, 如果完全经过单调栈下一位置 $v$, 那么 $s$ 经过 $v$ 的花费为 $f_u + \operatorname{depth}(v) \cdot (w_v - w_u)$.

(此处称之为 “花费” 并不完全准确, 因为此处的 depth 为到根节点的距离. 这样维护目的在于简化计算答案时分类讨论时的式子)

那么答案即可通过栈顶的 $f$ 算出, 并不要漏掉 $s$ 到 $t$ 的距离. 同时 $f$ 直接在加入一个节点时维护即可. 但是此时有多组询问. 直接离线处理, 从右向左, 对于每个节点依次维护单调栈即可.

再来推广到树的情况.

对于一轮从 $s$ 到 $t$ 的游戏, 每次都沿着 $s \rightarrow t$ 的路径前进, 直到能够到达 $t$ 的策略, 显然不是最优的: 我们可以在 $s$ 的子树内寻找一条深度较浅的点, 并通过在该点快速积累死亡次数, 从而减少在树上移动的时间.

而链上的情况并不存在其他儿子的子树, 因此可以不考虑这个问题. 在树的条件下, 维护单调栈的同时需要注意深度的影响.

栈中插入一个元素, 需满足栈中 $w_i$ 递增. 同时, 只在栈为空, 或是栈顶元素深度大于当前元素时插入. 这样就解决了上面的问题.

注意到单调栈的大小和子树中最深点的深度有关. 容易想到用长链剖分维护这个单调栈, 也就是直接继承长儿子的单调栈, 同时大力合并其他儿子的单调栈. 在合并时, 直接按照深度从小到大, 将一个栈中的元素插入另一个栈中即可.

计算答案则在栈内二分. 找到栈中某个点 $p$, 使其满足 $w_p \ge \max \{ {w_{s \rightarrow t} } \}$ (当然此处不包含 $s,t$). 注意不存在此位置的情况. 细节见代码实现.

而 hzy 的题解, 有一个称作 “队列启发式合并” 的技巧: 在 DFS 维护处理询问时, 按照 DFS 序分配在队列中的空间. 而每次合并后的结果, 一定不会超过 DFS 序所限定的范围, 并且是连续的. 这样就避免了较为繁琐的实现.

时间复杂度 $O(n\log n + q \log n)$.

代码实现

// UOJ #284
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

typedef long long LL;
const int MAXN = 3e5 + 5, LOG = 20;

struct Ask {
  int idx, t;
  Ask() = default;
  Ask(int _i, int _t): idx(_i), t(_t) { }
};

int n, q;
int pre[MAXN], W[MAXN];

int Mx[LOG][MAXN], anc[LOG][MAXN];
int depth[MAXN], son[MAXN], dfn[MAXN], clk;

LL Ans[MAXN];
vector<Ask> Q[MAXN];

namespace Graph {
  struct Edge { int nxt, to; } edges[MAXN];
  int head[MAXN], d[MAXN], eidx;

  inline void init() { memset(head, -1, sizeof head), eidx = 1; }
  inline void AddEdge(int from, int to) {
    edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
  }

  void dfs(int u) {
    depth[u] = depth[pre[u]] + 1;
    for (int j = 1; (1 << j) <= n; ++j) if (anc[j - 1][u] > 0) {
      anc[j][u] = anc[j - 1][anc[j - 1][u]];
      Mx[j][u] = max(Mx[j - 1][u], Mx[j - 1][anc[j - 1][u]]);
    }
    for (int v, i = head[u]; ~i; i = edges[i].nxt) {
      dfs(v = edges[i].to);
      if (d[v] > d[son[u]]) son[u] = v;
    }
    d[u] = d[son[u]] + 1;
  }

  inline void solve(int rt) {
    d[0] = -1;
    for (int u = 1; u <= n; ++u)
      Mx[0][u] = W[u], anc[0][u] = pre[u];
    dfs(rt);
  }
}

inline int QryMax(int u, const int& v) {
  int ret = 0;
  for (int j = LOG - 1; j >= 0; --j)
    if (depth[anc[j][u]] >= depth[v])
      ret = max(ret, Mx[j][u]), u = anc[j][u];
  return ret;
}

namespace Que {
  struct Node {
    int d, w;
    Node(int _d = 0, int _w = 0): d(_d), w(_w) { }
  } Qu[MAXN], stk[MAXN];

  LL s[MAXN];
  int Head[MAXN], Tail[MAXN];

  inline void newnode(const int& u, int head, int tail) {
    Head[u] = head, Tail[u] = tail;
  }

  void Ins(int u, const Node& v) {
    int &head = Head[u], &tail = Tail[u];
    while (head <= tail && Qu[head].w <= v.w) ++head;
    if (head > tail || Qu[head].d > v.d) {
      s[head - 1] = 0;
      if (head <= tail)
        s[head - 1] = s[head] + 1LL * Qu[head].d * (Qu[head].w - v.w);
      Qu[--head] = v;
    }
  }

  void Mrg(const int& u, const int& v) { // Qu[u] <-- Qu[v]
    int &hu = Head[u], &tu = Tail[u], &hv = Head[v], &tv = Tail[v];
    int top = 0;
    while (hu <= tu && Qu[hu].d < Qu[tv].d)
      stk[++top] = Qu[hu++];
    while (top > 0 && hv <= tv) {
      if (Qu[tv].d > stk[top].d) Ins(u, Qu[tv--]);
      else Ins(u, stk[top--]);
    }
    while (top > 0) Ins(u, stk[top--]);
    while (hv <= tv) Ins(u, Qu[tv--]);
  }
}

void dfs(int u) {
  using Graph::edges;
  dfn[u] = ++clk;
  if (son[u] > 0)
    dfs(son[u]), Que::newnode(u, Que::Head[son[u]], Que::Tail[son[u]]);
  else
    Que::newnode(u, clk, clk - 1);
  for (int v, i = Graph::head[u]; ~i; i = edges[i].nxt)
    if ((v = edges[i].to) != son[u]) dfs(v), Que::Mrg(u, v);
  for (const Ask& a: Q[u]) {
    using namespace Que;
    const int &head = Head[u], &tail = Tail[u];
    int L = head, R = tail, w = QryMax(pre[a.t], u);
    while (L < R) {
      int Mid = (L + R) / 2;
      if (Qu[Mid].w < w) L = Mid + 1; else R = Mid;
    }
    if (Qu[head].w <= w) {
      Ans[a.idx] += s[head] - s[L] + 1LL * Qu[head].d * Qu[head].w;
      Ans[a.idx] += 1LL * Qu[L].d * (w - Qu[L].w) - 1LL * w * depth[u];
    } else {
      Ans[a.idx] += 1LL * w * (Qu[L].d - depth[u]);
    }
    Ans[a.idx] += depth[a.t] - depth[u];
  }
  Que::Ins(u, Que::Node(depth[u], W[u]));
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("data/ex_rewrite3.in", "r", stdin);
#endif
  Graph::init();

  read(n);
  for (int i = 1; i <= n; ++i) read(W[i]);
  for (int i = 2; i <= n; ++i)
    read(pre[i]), Graph::AddEdge(pre[i], i);
  read(q);
  for (int s, t, i = 1; i <= q; ++i)
    read(s), read(t), Q[s].push_back(Ask(i, t));

  Graph::solve(1), dfs(1);

  for (int i = 1; i <= q; ++i)
    printf("%lld\n", Ans[i]);
  return 0;
}

我再也不做数据结构了.cpp

参考资料

• UOJ, Goodbye Bingshen 题解
• hzy, 题解-UOJ284 快乐游戏鸡

---