柿子饼同学 发表于 2024-8-25 14:26:45

[心之碎片] - 树上算法

包含{:10_266:}
树上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 深度越大, 所以排序 + 双指针
while (m--) {
    cin >> a;
    for (int i = 1; i <= a; i++) cin >> A;
    cin >> b;
    for (int i = 1; i <= b; i++) cin >> B;

    // 多测不清空, 亲人两行泪
    A = B = 0;
    sort(A + 1, A + a + 1, [](int x, int y) { return dfn < dfn; });
    sort(B + 1, B + b + 1, [](int x, int y) { return dfn < dfn; });

    int r = 0, ans = 0;
    for (int i = 1; i <= a; i++) {
      while (r + 1 <= b && dfn] < dfn]) r++;
      ans = max(ans, max(dep, B)], dep, B)]));
    }
    cout << ans << '\n';
}

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

    int a, b;
    auto p = st.upper_bound(dfn);

    if (p == st.begin() || p == st.end()) {
      a = rdfn[*st.begin()];
      b = rdfn[*st.rbegin()];
    } else {
      a = rdfn[*p];
      p--;
      b = rdfn[*p];
    }

    // 点 u 到链 的距离
    // if(dep > dep){
    //   u 在 lca(a, b) 上面的情况
    //   return (s + s - 2*s);
    // }
    // else{
    //   u 在下面, 通过 dep 判断应该连谁的 lca
    //   if(dep < dep) swap(a, b);
    //   return (s - s);
    // }

    // 下面这个是可以用路径长度推的
    // ans = (dis(a, x) + dis(b, x) - dis(a, b)) / 2, 用 lca 展开即可
    return (s - s - s + s);
}

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
struct Trie {
    int t, s, tot = 1, rt = 1;

    void Insert(int x, int v) {
      int p = rt, o;

      for (int i = 30; s += v, i >= 0; i--) {
            o = (x >> i) & 1;

            if (!t)
                t = ++tot;
            p = t;
      }
    }

    int Query(int x) {
      int p = rt, o, res = 0;

      for (int i = 30; i >= 0; i--) {
            o = (x >> i) & 1;

            if (s]) {
                res |= (1 << i);
                p = t;
            } else {
                p = t;
            }
      }

      return res;
    }
} trie;

// QTREE
int dfn, rdfn, tot;
int siz, hc;

void dfs0(int u) {
    dfn = ++tot;
    rdfn = u;
    siz = 1;

    for (auto v : e) {
      dfs0(v);
      siz += siz;
      if (siz] < siz)
            hc = v;
    }
}

// DSU on tree
void Modify(int x, int v) {
    for (int i = dfn; i < dfn + siz; i++) {
      trie.Insert(val], v);
    }
}

void Solve(int u) {
    for (auto v : e) {
      if (v == hc)
            continue;

      Solve(v);
      Modify(v, -1);
    }

    if (hc)
      Solve(hc);

    for (auto v : e) {
      if (v == hc)
            continue;

      Modify(v, 1);
    }
    trie.Insert(val, 1);

    for (auto x : ask) {
      ans = trie.Query(x.first);
    }
}

J - Race
板子题
void Solve(int u, int f) {
    for (auto y : e) {
      if (y.v == f || y.v == hc)
            continue;

      Solve(y.v, u);
      mp.clear();
    }

    if (hc)
      Solve(hc, u);

    for (auto y : e) {
      if (y.v == f || y.v == hc)
            continue;

      for (int i = dfn; i < dfn + siz; i++) {
            Checkmin(rdfn, u);
      }
      for (int i = dfn; i < dfn + siz; i++) {
            Add(rdfn);
      }
    }

    Checkmin(u, u);
    Add(u);
}

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

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

FishC 发表于 2024-8-25 14:27:09

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

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

### 树上基础算法

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

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

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序列，将树问题转化为线性问题，利用双指针法找出最优解。

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

while (m--) {
    cin >> a;
    vector<int> A(a);
    for (int i = 0; i < a; ++i) cin >> A;
   
    cin >> b;
    vector<int> B(b);
    for (int i = 0; i < b; ++i) cin >> B;
   
    sort(A.begin(), A.end(), [](int x, int y) { return dfn < dfn; });
    sort(B.begin(), B.end(), [](int x, int y) { return dfn < dfn; });
   
    int ans = 0;
    int i = 0, j = 0;
    while (i < a && j < b) {
      ans = max(ans, depth, B)]);
      if (dfn] < dfn]) ++i;
      else ++j;
    }

    cout << "最大LCA深度: " << ans << endl;
}

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

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

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

学习编程中的Ben 发表于 2024-8-25 14:29:50

厉害

很cool的阳 发表于 2024-8-26 09:32:56

{:7_113:}

18408238295 发表于 2024-8-26 10:41:27

学习学习

zsy0226 发表于 2024-8-29 09:13:04

{:7_113:}

简柠啦 发表于 2024-8-31 16:38:47

{:10_266:}{:10_266:}

trinityee 发表于 2024-9-1 09:57:18

学习再学习{:10_254:}

森林格格屋 发表于 2024-9-4 16:01:20

谢谢

XiaoMengXin-1 发表于 2024-9-14 17:38:42

鱼币！

cc885544 发表于 2024-10-7 22:50:27


学习再学习
页: [1]
查看完整版本: [心之碎片] - 树上算法