[心之碎片] - 树上算法

柿子饼同学

包含
树上dfs序 树上倍增 树链剖分 树上启发式合并

应该先判断是否连通...

树上问题先想低级算法 :
dfs栈 (把之前的祖先节点放进栈中, 双指针或者二分什么的)  
树上差分 (点上加东西, 在 lca 和 lca 父节点各自减去一个)
dfs做差 (递归进入子树之前先记录当前的答案, dfs回来之后再记录当前的答案, 这样两个相减就是子树答案了)
树上倍增

树上问题的一些思考 :
lca单调性 (一个点是否是 lca 具有单调性 0000011111...)
善用 dfn 的有序性, 把无序变成有序, 把树上转换为序列
自己画图找性质
dfn 越近, lca深度越深
树上的函数 : lca, dist(点点距, 点链距), up(倍增向上跳), Insub(用 dfn 判断是否在子树中)
树上的路径分类: u 到 祖先, 祖先到 u
dep 就是 root 到 u 的 dis

一些题

B - LCA查询
给一个树, 每次询问给出两个集合 A, B, 让你求出在两个集合中各选一个点的 lca 深度最大是多少

可以二分深度, 对于每个 A 中的点向上跳这么多距离并且标记, 然后对于 B 也是往上跳, 如果能遇到标记说明这个 lca 深度是可行的 (lca单调性)
更简单的做法是利用 dfn, dfn 近的点 lca 深度越大, 所以排序 + 双指针

1. while (m--) {
   
2.     cin >> a;
   
3.     for (int i = 1; i <= a; i++) cin >> A[i];
   
4.     cin >> b;
   
5.     for (int i = 1; i <= b; i++) cin >> B[i];
   
6. 
   
7.     // 多测不清空, 亲人两行泪
   
8.     A[a + 1] = B[b + 1] = 0;
   
9.     sort(A + 1, A + a + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
   
10.     sort(B + 1, B + b + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
    
11. 
    
12.     int r = 0, ans = 0;
    
13.     for (int i = 1; i <= a; i++) {
    
14.         while (r + 1 <= b && dfn[B[r + 1]] < dfn[A[i]]) r++;
    
15.         ans = max(ans, max(dep[lca(A[i], B[r])], dep[lca(A[i], B[r + 1])]));
    
16.     }
    
17.     cout << ans << '\n';
    
18. }

复制代码

C - 动态造树
考虑把一个点连到树中, 可以知道应该是 dfn 相邻的两个点形成的路径到这个点的距离是最小的
所以用 set 维护加进来节点的 dfn , 每次查询和 x 相邻的两个点然后连边 (点链距)

1. int Work(int u) {
   
2.     if (st.empty())
   
3.         return 0;
   
4. 
   
5.     int a, b;
   
6.     auto p = st.upper_bound(dfn[u]);
   
7. 
   
8.     if (p == st.begin() || p == st.end()) {
   
9.         a = rdfn[*st.begin()];
   
10.         b = rdfn[*st.rbegin()];
    
11.     } else {
    
12.         a = rdfn[*p];
    
13.         p--;
    
14.         b = rdfn[*p];
    
15.     }
    
16. 
    
17.     // 点 u 到链 [a, b] 的距离
    
18.     // if(dep[Lca(a, b)] > dep[Lca(a, u)]){
    
19.     //     u 在 lca(a, b) 上面的情况
    
20.     //     return (s[u] + s[Lca(a, b)] - 2*s[Lca(Lca(a, b), u)]);
    
21.     // }
    
22.     // else{
    
23.     //     u 在下面, 通过 dep 判断应该连谁的 lca
    
24.     //     if(dep[Lca(a, u)] < dep[Lca(b, u)]) swap(a, b);
    
25.     //     return (s[u] - s[Lca(a, u)]);
    
26.     // }
    
27. 
    
28.     // 下面这个是可以用路径长度推的
    
29.     // ans = (dis(a, x) + dis(b, x) - dis(a, b)) / 2, 用 lca 展开即可
    
30.     return (s[u] - s[Lca(a, u)] - s[Lca(b, u)] + s[Lca(a, b)]);
    
31. }

复制代码

D - BZOJ3306 树
板子题, 只需要判断现在的根和询问的 x 子树关系即可

F - 树上交易
每个节点有一个商品的价格，可以买入或者卖出。
询问从一个节点到另一个节点，可以在路途中买入和卖出一次，求最大收益。

线段树维护区间 min, max(区间最大最小值), down, up(向上或者向下走的卖一次的收益)

G - Duff in the Army
树剖板子题, 也可以倍增, 每次归并两个 vector

接下来是几个 dsu on tree
总体步骤就是
1. 计算轻孩子, 删除
2. 计算重孩子
3. 把轻孩子的贡献加进来, 更新答案
4. 把 u 加进来, 更新答案

I - HDU6191
01 字典树处理抑或, dsu

1. struct Trie {
   
2.     int t[N * 30][2], s[N * 30], tot = 1, rt = 1;
   
3. 
   
4.     void Insert(int x, int v) {
   
5.         int p = rt, o;
   
6. 
   
7.         for (int i = 30; s[p] += v, i >= 0; i--) {
   
8.             o = (x >> i) & 1;
   
9. 
   
10.             if (!t[p][o])
    
11.                 t[p][o] = ++tot;
    
12.             p = t[p][o];
    
13.         }
    
14.     }
    
15. 
    
16.     int Query(int x) {
    
17.         int p = rt, o, res = 0;
    
18. 
    
19.         for (int i = 30; i >= 0; i--) {
    
20.             o = (x >> i) & 1;
    
21. 
    
22.             if (s[t[p][o ^ 1]]) {
    
23.                 res |= (1 << i);
    
24.                 p = t[p][o ^ 1];
    
25.             } else {
    
26.                 p = t[p][o];
    
27.             }
    
28.         }
    
29. 
    
30.         return res;
    
31.     }
    
32. } trie;
    
33. 
    
34. // QTREE
    
35. int dfn[N], rdfn[N], tot;
    
36. int siz[N], hc[N];
    
37. 
    
38. void dfs0(int u) {
    
39.     dfn[u] = ++tot;
    
40.     rdfn[tot] = u;
    
41.     siz[u] = 1;
    
42. 
    
43.     for (auto v : e[u]) {
    
44.         dfs0(v);
    
45.         siz[u] += siz[v];
    
46.         if (siz[hc[u]] < siz[v])
    
47.             hc[u] = v;
    
48.     }
    
49. }
    
50. 
    
51. // DSU on tree
    
52. void Modify(int x, int v) {
    
53.     for (int i = dfn[x]; i < dfn[x] + siz[x]; i++) {
    
54.         trie.Insert(val[rdfn[i]], v);
    
55.     }
    
56. }
    
57. 
    
58. void Solve(int u) {
    
59.     for (auto v : e[u]) {
    
60.         if (v == hc[u])
    
61.             continue;
    
62. 
    
63.         Solve(v);
    
64.         Modify(v, -1);
    
65.     }
    
66. 
    
67.     if (hc[u])
    
68.         Solve(hc[u]);
    
69. 
    
70.     for (auto v : e[u]) {
    
71.         if (v == hc[u])
    
72.             continue;
    
73. 
    
74.         Modify(v, 1);
    
75.     }
    
76.     trie.Insert(val[u], 1);
    
77. 
    
78.     for (auto x : ask[u]) {
    
79.         ans[x.second] = trie.Query(x.first);
    
80.     }
    
81. }

复制代码

J - Race
板子题

1. void Solve(int u, int f) {
   
2.     for (auto y : e[u]) {
   
3.         if (y.v == f || y.v == hc[u])
   
4.             continue;
   
5. 
   
6.         Solve(y.v, u);
   
7.         mp.clear();
   
8.     }
   
9. 
   
10.     if (hc[u])
    
11.         Solve(hc[u], u);
    
12. 
    
13.     for (auto y : e[u]) {
    
14.         if (y.v == f || y.v == hc[u])
    
15.             continue;
    
16. 
    
17.         for (int i = dfn[y.v]; i < dfn[y.v] + siz[y.v]; i++) {
    
18.             Checkmin(rdfn[i], u);
    
19.         }
    
20.         for (int i = dfn[y.v]; i < dfn[y.v] + siz[y.v]; i++) {
    
21.             Add(rdfn[i]);
    
22.         }
    
23.     }
    
24. 
    
25.     Checkmin(u, u);
    
26.     Add(u);
    
27. }

复制代码

K - GSS7
树剖 + 线段树维护最大字段和板子题

L - 天天爱跑步
树上差分 + dfs 做差 + 路径分类

FishC

#### 鱼油的问题：树上算法

感谢鱼油提出的这个问题，让我们看看如何更清晰地理解树上算法的一些内容。

### 树上基础算法

先决条件是判断是否连通，这是树上问题的基础保证。

一些常用的树上算法和技巧包括：

1. **DFS栈**：可以用来遍历树，访问每一个节点。维护一个栈保存当前路径的祖先节点。
2. **树上差分**：进行区间操作非常高效。可以在LCA（最近公共祖先）和LCA的父节点上执行加减操作，实现区间加减。
3. **DFS做差**：用于计算子树的问题。在进入子树前记录当前状态，离开子树后再次记录，两者之差即为该子树的答案。
4. **倍增法**：用来解决LCA查询，构造一个倍增表，每次跳特定的步数以达到快速查询的效果。

### 树上的LCA（最近公共祖先）问题

#### 树上LCA单调性

LCA问题具有单调性，即一个点是否是另一个点的LCA是具有单调性的。例如：0000011111。这可以用于二分查找，以对LCA进行一些优化。

#### Dfn有序性

通过DFS序（dfn），将树形结构转化为一个线性序列，方便进行排序和其他有序操作。例如，dfn值越近，则LCA的深度越深。

### 树上的路径和深度

- `dep`表示根节点到某个节点u的距离。
- 一些常用的树上操作函数：
  - `lca(x, y)`: 查询x和y的最近公共祖先。
  - `dist(u, v)`: 查询u和v的距离或路径长度。
  - `up(u, k)`: 从节点u向上跳k个节点。
  - `Insub(x, y)`: 判断y是否在x的子树中，通常通过dfn序列实现。

### 样例题目

#### B - LCA查询
问题描述：给出一个树，每次查询两个集合A和B，求出在两个集合中各选一个点的LCA深度最大是多少。

解决思路：
1. **暴力解法**：对于每个集合A中的点向上跳一定的距离并标记，然后对B集中的点也进行类似操作，看能否遇到标记。通过二分法判断这个深度是否可行。
2. **优化解法**：排序Dfn序列，将树问题转化为线性问题，利用双指针法找出最优解。

代码实现可以按照以下思路进行：

1. while (m--) {
   
2.     cin >> a;
   
3.     vector<int> A(a);
   
4.     for (int i = 0; i < a; ++i) cin >> A[i];
   
5.    
   
6.     cin >> b;
   
7.     vector<int> B(b);
   
8.     for (int i = 0; i < b; ++i) cin >> B[i];
   
9.    
   
10.     sort(A.begin(), A.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
    
11.     sort(B.begin(), B.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
    
12.    
    
13.     int ans = 0;
    
14.     int i = 0, j = 0;
    
15.     while (i < a && j < b) {
    
16.         ans = max(ans, depth[lca(A[i], B[j])]);
    
17.         if (dfn[A[i]] < dfn[B[j]]) ++i;
    
18.         else ++j;
    
19.     }
    
20. 
    
21.     cout << "最大LCA深度: " << ans << endl;
    
22. }

复制代码

注意：这是个示例，实际代码实现中需要定义并初始化 `dfn` 和 `depth` 以及相应的数据结构和输入处理。

通过这些说明，相信您对树上算法有了初步的理解。祝您学习顺利！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

学习编程中的Ben

厉害

很cool的阳

18408238295

学习学习

zsy0226

简柠啦

trinityee

学习再学习

森林格格屋

谢谢

XiaoMengXin-1

鱼币！

cc885544

学习再学习