Atcoder abc351

發表於 更新於 分類於 ， Disqus： 文章字數： 4.8k 所需閱讀時間 ≈ 16 分鐘
G(top tree, static top tree)

https://atcoder.jp/contests/abc351

G - Hash on Tree

给定n点树有根数

值数组a[n]

f(u) = a[u] , 如果u是叶子

f(u) = a[u] + prod f(child of u)如果u非叶子

q次操作,每次 修改 a[pos]=val,每次修改后输出 f(1)

n,q 2e5

4s

1024mb

我的思路

首先这个是收到深度控制的,如果暴力的更新的话

那么一个想法是能否flat掉这个行为

[a,b,c]x[x,y,1] = [0,a*1+b*y,1]

leaf = [0,ai,1]

非叶子 = [ai,1,0]

然而没找到 矩阵方法或者满足“结合率”的东西

如果能有 矩阵或者结合律满足，就是个线段树维护，就好了

其中 上面的乘还可以拆成左右的包裹，总之如果有办法就好了

但是在尝试中发现要得到 a1+by 这种总是伴随秩的下降，没啥办法

第二个想的是上生成方程, 也没有弄出东西

那么最后就是 能否树的结构通过 轻重链 来完成快速计算(q log n)? 也没想到具体维护方法

题解

有很多解法，官方用的一个数据结构叫做 Static top tree.

TLDR

感觉这题解详细但没强调关键，稍微总结一下下面

  • 切分方案(点u和它的子树) = 点u的重链 和 点u的轻儿子们
    • 线段树的中间状态是一个区间，而这里中间状态有两种
      • 第一种状态：重链的连续的一段 和 这些点的所有亲儿子，这在下面叫做 path cluster
      • 第二种状态：点u和它的轻儿子的 连续的一段， 这在下面叫做 point cluster
类似的 这里
用 线段树 管理区间 点修改 和 区间查询 用static top tree 管理 静态的tree dp
线段树的非叶子结点，或者查询结果对应一个区间的状态 static top tree的非叶子结点，或查询结果对应 一个point cluster/path cluster
数链剖分 揭露了重轻链 的复杂度优势 这里也用了类似优势
线段树的状态是 根据你需要设计的 这里也是根据你需要设计的，只是因为有两种形式，所以这里有两种状态需要设计
线段树的节点状态/查询状态 = 两个子状态的符合 这里也需要复合，不过这里复合的子状态来源有5种

5种子状态符合

  • 单点: vertex(g中的点)->path
  • 重链上相邻两段复合: compress(path l,path r) -> path
  • 一个节点的 连续轻儿子复合: rake(point l,point r) -> point
  • 点u的完整子树 变为 点u父节点的 单个亲儿子: add_edge(path) -> point
  • 点u的轻儿子 变成 点u为重链上的一个单点: add_vertex(point,g中的点) -> path

自底向上看就是

  • 一个点加入它所属于的重链
    • 它自身无轻儿子: compress(compress(…compress(vertex(u))))
    • 有轻儿子, compress(compress(…compress(add_vertex(rake(rake(…它的轻儿子们的二叉树)), u))))
  • 一个点加入它不属于的上层重链
    • 首先它会 按照上面的过程加入到它属于的重链，得到一个 path cluster, 令其为POINT
    • 然后 add_vertex(rake(rake(…rake(add_edge(POINT))))) 变成一个 更上层重链的一个单点PATH
    • 最后 compress(compress(…compress(PATH)))
1
2
3
4
5
6
function 切割(u 和它的子树):
  arr = [
    (对([切割(w) for w in v的亲儿子们])构建按重量分割的二叉树)
    for v in u的重链
  ]
  return 对arr构建按重量分割的二叉树

本题的point cluster可以表述成单个值

而path cluster可以表述成 ax+b的形式，其中x指代的是 当前path向叶子延伸被截断的重链的部分

目标: 在 线段树上管理一个树的DP

首先,考虑解决这个问题的必要操作

首先考虑O(N)时间解决每个查询, 这很简单，就是树上DP,显然TLE

如果能转化成序列问题

  • 修改 a[i]=x
  • 查询 $A_1\oplus A_2\oplus \cdots \oplus A_N$

若能转化，则可以segtree维护

观察 1: 对于 perfect binary tree

然后就是 树上dp+记忆化+从节点到根的更新dp，因为 perfect binary tree, 所以深度在log级别，总时间复杂度为 O(q log n)

观察 2: decomposition of tree 和 tree DP的关系

为了展开观察，我们将从另一个角度来解释树状 DP。 事实上，树状图 DP 可以看作是通过合并子树生成有根树的过程，同时保留了一些信息。 现在我们来描述一下这一特性。

在考虑通过合并生成树的过程时，有必要考虑反向操作：分解树的过程。 因此，我们首先考虑分解树的过程。 通过递归执行下面的(1)-(3)直到树上没有边为止，我们就可以把一棵有根树分解成顶点和边。 参见下图。

  • (1) 删除一个根顶点。 在这里，不要删除与根顶点相邻的边，因为这些边的端点被认为是一个没有信息的顶点（我们称这样的顶点为虚拟顶点）。
  • (2) 通过克隆虚拟顶点，分割出虚拟顶点连接的子树。
  • (3) 从每条子树中删除虚拟顶点及其相邻的边。 现在，每个子树都形成了一个普通顶点。

atcoder example image 0

按照相反的顺序，子树逐渐合并，最终形成一棵有根的树。

让我们用函数来表示合并过程。 定义以下四个函数。 在下文中，我们假定顶点附有信息且可区分，但边不附有信息且不可区分。

  • vertex(v): 生成 点v
  • add_vertex(t,v): 1的反向操作, 令 点v 是 树t 的virtual root
  • merge(x,y): 2的反向操作, 把树x,树y的通过virtual节点合并成一个
  • add_edge(t): 3的反向操作, 给有根树t 增加一个 virtual root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> g; // 邻接表

Tree generate_tree(int v) {// 生成根为v的子树，子节点是临接表中的
  if(g[v].empty()) return vertex(v);
  vector<Tree> children;
  for(auto& child : g[v]) {
    Tree t = generate_tree(child);
    children.push_back(add_edge(t));
  }
  Tree t = children[0];
  for(int i = 1; i < (int)children.size(); i++) {
    t = merge(t, children[i]);
  }
  return add_vertex(t, v);
}

对于这里来说

1
2
3
4
5
6
using mint = atcoder::modint998244353;
using T = mint;
T vertex(int v) { return A[v]; }
T add_vertex(T x, int v) { return x + A[v]; }
T merge(T x, T y) { return x * y; }
T add_edge(T x) { return x; }

wow !!! 有点东西，抽象出来之后 这是有点神奇

这样来看, 树状DP 可以看作 通过合并子有根树 来生成一个新的有根树的过程。

  • 从叶顶点开始，考虑通过重复执行以下三种操作来合并子树：添加顶点、添加边以及合并根为虚拟顶点的根树。
  • 一般树具有以下两个特性，它们阻碍了高效的重新计算
    • 长度最坏O(N)
    • 子节点最坏O(N)
  • 顺便说一下，树形 DP 是一个合并子树的过程，同时保留一些信息
    • 合并子树的过程可以按照合并子树的逆操作生成。

这两个事实产生了以下结果：

  • 如果我们能以二叉树的形式生成深度为 O(logN)的合并过程，那么树 DP 是否可以高效地重新计算呢？

这种合并过程的实现就是static top tree。

static top tree

注：虽然 Static top tree 的名称是 “Top tree”，但它与 Top tree（狭义）是完全不同的数据结构。 如果你想学习 Top 树，请不要混淆。

  • 更确切地说，静态顶层树是 “支持顶层树大部分功能的数据结构的静态版本，这种数据结构是通过管理 Splay 树中链接/切割树上的正常边所维护的信息来实现的”（广义的顶层树）。
    • 顺便说一下，我们还可以通过将一棵 Top 树（狭义上）变为静态来构建静态顶树。 有人将这种数据结构称为静态顶树。 我们在此跳过对它的介绍，但如果你有兴趣，请参阅 tatyam 的实现和注释(日语) https://atcoder.jp/contests/joisp2024/submissions/51887735

静态顶树是一棵深度为 O(logN)的二叉树，表示合并子树（实际上不是子树，稍后描述）的过程。

为了说明如何构建静态顶树，我们首先解释合并过程的逆操作，即分解树的过程。 首先，对树应用 HLD 将每条边分为重边和轻边。 （如果您不了解 HLD，请参阅 ABC269 Ex 的题解）。

然后，重复以下步骤 (1)-(4) 直到树上没有边为止。

  • (1) 选择与根相连的重路径，并删除其中的重边
  • (2) 删除根顶点。 这里，不要删除与根相邻的边，因为这些边的端点被视为虚拟顶点。
  • (3) 通过克隆虚拟顶点，将虚拟顶点连接的子树分割开来。
  • (4) 从每个子树上删除虚拟顶点及其相邻的轻边。 现在每个子树都形成了一个普通顶点。

atcoder 1-4 示例图

值得注意的是，分解过程中出现的图形不一定是有根树的子树。 也就是说，在步骤(1)中去除边后，可能会出现一个不能被视为有根树的图，这取决于去除边的顺序。 我们借用 “顶树 “这一术语，将分解过程中出现的图形称为cluster。

如图所示，分解过程中会出现以下两种cluster：

  • 以非虚拟顶点为根的子树由零条或多条重边连接的cluster
  • 形成以虚拟顶点为根的子树的cluster。

atcoder 示例图 path cluster, point cluster

接下来，我们按照分解的逆操作，想出一种将cluster并为二叉树形式的方法。在分解过程中，会发生两种cluster合并：合并path cluster和合并point cluster。我们进一步借用 Top tree 的术语，将前者称为 compress，将后者称为 rake。

static top tree的关键是在将cluster合并为二叉树形式时应用技巧，将深度保持在$O(\log N)$。但是，在 (2) 和 (4) 的逆运算中没有技巧的余地；我们可以改进的是逆运算：

-（1）选择一条重路径并从中移除重边；
-（3）通过克隆虚拟顶点来分离与虚拟顶点相连的子树。

直观地看，按照以下策略合并集群似乎是一个好主意：

  • (1) 的逆操作：在“compose” path culsters时，确保合并过程形成完美的二叉树。
  • (3) 的逆操作：在“rake”-ing path clusters时，确保合并过程形成完美的二叉树。

这是一个非常合理的策略，因为一般树的两个属性阻碍了高效的计算：

  • 深度$O(N)$
  • 子节点$O(N)$

分别通过compressing和raking实现

在这种策略下，最差的的深度可能达到 $O(\log^2 N)$ 我们在此省略细节。原因与使用 HLD + 线段树处理路径查询的简单实现在最坏情况下成本为 $O(\log^2 N)$ 的性质相同。

这就是为什么我们需要另一种ingeuity。“合并cluster以形成完美的二叉树”意味着“合并以使左右子节点具有（几乎）相同顶点的cluster。”事实上，我们可以证明后一种策略允许我们将整个合并过程的深度保持在 O(logN), （我们也省略了细节。原因与在最坏的情况下用 HLD + 线段树在
O(logN) 时间内处理路径查询的想法相同。参考：Nachia 的文章（日语）https://www.mathenachia.blog/mergetech-and-logn/ ，errorgorn 的文章中的“平衡 HLD”一章 https://codeforces.com/blog/entry/104997。）

通过上述技巧，合并cluster的过程可以用深度为O(logN) 的二叉树来表示。

示例代码 https://atcoder.jp/contests/abc351/submissions/52777033（第 5 - 74 行）：我们参考了 maspy 和 tatyam 的实现。

原始问题的解

现在我们用static top tree来描述原始问题的解决方案。

合并cluster时需要以下五个函数：

  • vertex(v)：生成仅由顶点 v 组成的path cluster的函数。
  • compress(p, c)：执行 (1) 逆操作的函数，即合并path cluster p 和 c（其中 p 更靠近根）。
  • add_vertex(t, v)：执行 (2) 逆操作的函数，即把顶点 v 分配给path cluster t 的根以形成新的path cluster。
  • rake(x, y)：执行 (3) 逆操作的函数，即合并point cluster x 和 y。
  • add_edge(t)：执行 (4) 逆操作的函数，即向path cluster t 添加虚拟根以形成point cluster。

和树型DP一样，该问题可以通过定义树上需要存储的信息，以及构造与这五个函数对应的DP转换来解决。

其中最难的是压缩，即合并path cluster。虽然合并point cluster在某种程度上可以看作是树DP的扩展，可以通过存储相同的信息来执行rake来实现，但合并path cluster意味着合并“特殊形状”的对象。

这里，我们采用 Top tree的术语，将cluster外另一个cluster的顶点旁边的cluster顶点称为boundary顶点。path cluster基本上有两个boundary顶点，一个靠近根，一个离根更远。（当path cluster是根树时会出现例外，其中两个边界顶点指向同一个顶点。）根据问题，人们可以相对轻松地通过关注这两个边界顶点来构建 DP 的转换。

经过适当的观察，可以发现path cluster必须存储 (a,b) 的值，使得“当哈希值为 x 的子树合并到以距离根较远的boundary顶点为根的子树时，以更靠近根的边界顶点为根的子树变为 ax+b”。通过像这样定义path cluster上的信息，compress 可以定义为 affine function 的组合。我们还可以定义其他函数，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
using mint = atcoder::modint998244353;

vector<int> A;
struct Path {
  mint a, b;
};
using Point = mint;
Path vertex(int i) { return {1, A[i]}; }
Path compress(Path p, Path c) { return {p.a * c.a, p.a * c.b + p.b}; };
Point rake(Point l, Point r) { return l * r; };
Point add_edge(Path d) { return d.b; };
Path add_vertex(Point d, int i) { return {d, A[i]}; };

适当抽象一棵静态顶树，任何问题都基本可以通过定义上述五个函数来解决，这跟线段树的抽象只需要两个函数很像吧？

顺便说一下，线段树最初似乎被定义为不仅针对完美二叉树，而且针对一般的平衡二叉树的算法。（参考 https://kmyk.github.io/blog/blog/2020/03/04/segment-tree-is-not-complete-binary-tree/ ，日语）根据这种解释，使用静态顶树更新树DP可以被认为有点类似于线段树。

剩下的就是处理查询；这可以通过适当计算和更新 DP 来完成。

Sample code (line 76 - 134) https://atcoder.jp/contests/abc351/submissions/52777033

Further application of a Static top tree

TODO

代码

https://atcoder.jp/contests/abc351/submissions/58166606

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD = 998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read() { ll r;scanf("%lld", &r);return r; }

enum Type { Vertex_NoLightChild, Compress_HeavyChainInner, Rake_LightChildInner, AddEdge_LightPath, AddVertex_Vertex2LightChilds };

// g must be a rooted tree
struct StaticTopTree {
  vector<vector<int>>& g; // g是有根树,因此 g中需要保证只有 父->子的边
  int g_root;           // g中root的index
  int stt_root;         // an index of the root in static top tree
  vector<int> P, L, R;  // 在stt中的 父节点, 左儿子, 右儿子, 其中 [0,n) 和 g中的[0,n) 对应
  vector<Type> T;       // 节点类型
  int add_buf;          // a variable for the member function

  using id_sz = pair<int, int>;

  StaticTopTree(vector<vector<int>>& _g, int _root = 0) : g(_g), g_root(_root) {
    int n = g.size();
    P.resize(4 * n, -1);
    L.resize(4 * n, -1);
    R.resize(4 * n, -1);
    T.resize(4 * n, Type::Vertex_NoLightChild);
    add_buf = n; // 为了stt中[0,n) 和g中[0,n)对应
    build();
  }

private:
  int dfs(int u) { // 重链移到首位
    int su = 1;
    int smax = 0;
    for (int& v : g[u]) {
      int sv = dfs(v);
      su += sv;
      if (smax < sv) swap(v, g[u][0]);
      smax = max(smax, sv);
    }
    return su;
  }
  int add(int o/*在stt中的id*/, int l/*左儿子*/, int r/*右儿子*/, Type t /*类型*/) { // return stt index
    if (o == -1) o = add_buf++; // 可以用vector 动态增加 size得到 index简化
    P[o] = -1;
    L[o] = l;
    R[o] = r;
    T[o] = t;
    if (l != -1) P[l] = o;
    if (r != -1) P[r] = o;
    return o;
  }
  id_sz merge(const vector<id_sz>& arr, Type t) {
    // 整个功能，就是把 id_sz 数组 合并成 平衡的二叉树, 
    if (arr.size() == 1) return arr[0];
    int tot = 0;
    for (auto& [_, sz] : arr) tot += sz;
    vector<id_sz> l_half, r_half;
    for (auto& [u, sz] : arr) {
      (tot > sz ? l_half : r_half).emplace_back(u, sz);
      tot -= sz * 2;
    }
    auto [i, si] = merge(l_half, t);
    auto [j, sj] = merge(r_half, t);
    return { add(-1, i, j, t), si + sj };
  }
  id_sz compress(int u) { // 处理u开始的重链 u in g, return {i in stt, ?}
    vector<id_sz> heavychain{ add_vertex(u) }; // chs 存储 从u开始到叶子的重链
    while (!g[u].empty()) heavychain.push_back(add_vertex(u = g[u][0]));
    return merge(heavychain, Type::Compress_HeavyChainInner);
  }
  id_sz rake(int u) { // 处理u的轻儿子
    // 无轻儿子的点 {-1, 0}
    // 有轻儿子的点 merge(compress(儿子) for 儿子 in 轻儿子)
    vector<id_sz> lightedges;
    for (int i = 1; i < (int)g[u].size(); i++) { // 轻儿子
      auto [j, sj] = compress(g[u][i]);
      lightedges.push_back({ add(-1, j, -1, Type::AddEdge_LightPath), sj }); // 这里就是compress的size
    }
    return lightedges.empty() ? make_pair(-1, 0) : merge(lightedges, Type::Rake_LightChildInner);
  }
  id_sz add_vertex(int u) {
    auto [j, sj] = rake(u);
    return { add(u/* [0,n) g和stt是一一对应 */, j, -1, j == -1 /* 无轻儿子 */ ? Type::Vertex_NoLightChild : Type::AddVertex_Vertex2LightChilds), sj + 1 }; // 这里size+1, 也就是每个g上的点 只在stt中被记录一次，而那一次是在处理重链时的add_vertex
  }
  void build() {
    dfs(g_root);
    stt_root = compress(g_root).first;
  }
};

vector<int> A;
struct Path { // path cluster
  mint a, b; // ax+b
};
using Point = mint; // point cluster
Path vertex(int i) { return { 1, A[i] }; }
Path compress(Path p, Path c) { return { p.a * c.a, p.a * c.b + p.b }; }; // (p.a(c.a x+c.b)+p.b), p更靠近根
Point rake(Point l, Point r) { return l * r; };
Point add_edge(Path d) { return d.b; };
Path add_vertex(Point d, int i) { return { d, A[i] }; };

int main() {
  int N = read();
  int Q = read();
  vector<vector<int>> g(N);
  rep(i, 1, N) g[read() - 1].push_back(i);
  A.resize(N);
  rep(i, 0, N) A[i] = read();

  StaticTopTree stt{ g };
  vector<Path> path(stt.L.size()); // path cluster
  vector<Point> point(stt.L.size()); // point cluster

  auto update = [&](int k) {
    if (stt.T[k] == Type::Vertex_NoLightChild) {
      path[k] = vertex(k);
    } else if (stt.T[k] == Type::Compress_HeavyChainInner) {
      path[k] = compress(path[stt.L[k]], path[stt.R[k]]);
    } else if (stt.T[k] == Type::Rake_LightChildInner) {
      point[k] = rake(point[stt.L[k]], point[stt.R[k]]);
    } else if (stt.T[k] == Type::AddEdge_LightPath) {
      point[k] = add_edge(path[stt.L[k]]);
    } else if (stt.T[k] == Type::AddVertex_Vertex2LightChilds) {
      path[k] = add_vertex(point[stt.L[k]], k);
    } else {
      assert(false);
    }
    };
  auto dfs = [&](auto rc, int k) -> void {
    if (stt.L[k] != -1) rc(rc, stt.L[k]);
    if (stt.R[k] != -1) rc(rc, stt.R[k]);
    update(k);
    };
  dfs(dfs, stt.stt_root);

  while (Q--) {
    int v = read() - 1;
    int x = read();
    A[v] = x;
    while (v != -1) {
      update(v);
      v = stt.P[v];
    }
    printf("%d\n", path[stt.stt_root].b.val());
  }
  return 0;
}

参考+总结

评分是 2920

https://atcoder.jp/contests/abc351/editorial/9899

我看luogu题解好像还是有人用矩阵搞出来了

中文的static top tree似乎叫这个 全局平衡二叉树 https://oi-wiki.org/ds/global-bst/

https://www.luogu.com.cn/article/ef36ensd

相关练习 https://www.luogu.com.cn/problem/P4719

https://oi-wiki.org/ds/top-tree/

hld in atcoder abc 269 ex https://yexiaorain.github.io/Blog/atcoder/abc/269/

https://negiizhao.blog.uoj.ac/blog/4912

可视化 https://maomao9-0.github.io/static-top-tree-visualisation

https://wenku.baidu.com/view/75906f160b4e767f5acfcedb.html

luogu 4211 全局平衡二叉树 https://www.luogu.com.cn/problem/P4211

luogu P3384 【模板】重链剖分/树链剖分 https://www.luogu.com.cn/problem/P3384