[心之碎片] - 树上算法

柿子饼同学

包含
树上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[i];
    cin >> b;
    for (int i = 1; i <= b; i++) cin >> B[i];

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

    int r = 0, ans = 0;
    for (int i = 1; i <= a; i++) {
        while (r + 1 <= b && dfn[B[r + 1]] < dfn[A[i]]) r++;
        ans = max(ans, max(dep[lca(A[i], B[r])], dep[lca(A[i], B[r + 1])]));
    }
    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[u]);

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

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

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

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[N * 30][2], s[N * 30], tot = 1, rt = 1;

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

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

            if (!t[p][o])
                t[p][o] = ++tot;
            p = t[p][o];
        }
    }

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

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

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

        return res;
    }
} trie;

// QTREE
int dfn[N], rdfn[N], tot;
int siz[N], hc[N];

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

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

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

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

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

    if (hc[u])
        Solve(hc[u]);

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

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

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

J - Race
板子题

void Solve(int u, int f) {
    for (auto y : e[u]) {
        if (y.v == f || y.v == hc[u])
            continue;

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

    if (hc[u])
        Solve(hc[u], u);

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

        for (int i = dfn[y.v]; i < dfn[y.v] + siz[y.v]; i++) {
            Checkmin(rdfn[i], u);
        }
        for (int i = dfn[y.v]; i < dfn[y.v] + siz[y.v]; i++) {
            Add(rdfn[i]);
        }
    }

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

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

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

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

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

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

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

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

学习编程中的Ben

厉害

很cool的阳

18408238295

学习学习

zsy0226

简柠啦

trinityee

学习再学习

森林格格屋

谢谢

XiaoMengXin-1

鱼币！

cc885544

学习再学习