题目分析

题意理解

我们有一棵动态生长的树，需要处理两种操作：

1. 添加节点：在已有节点 u 上连接新节点 v
2. 查询距离：在谷图 G(T) 中查询 u 到 v 的最短距离

关键概念：谷图

谷图 G(T) 的定义：存在边 (u,v) 当且仅当在树 T 中，u 到 v 的路径上不存在异于 u,v 的点 x 满足 x > min(u,v)。

直观理解：两个节点能直接跳跃的条件是它们路径上的所有中间节点编号都小于等于 min(u,v)。

算法思路

整体框架：LCT + 树链剖分

1. 预处理阶段

• 构建最终的树结构
• 进行树链剖分，计算 LCA 等信息

2. 动态维护谷图连通性

使用 Link-Cut Tree (LCT) 维护：

• 节点的父子关系
• 路径上的最大编号节点
• 跳跃边的信息

3. 查询处理

对于查询 u 到 v：

• 找到路径上的关键点（最大编号节点）
• 计算在谷图中的跳跃次数

代码结构详解

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

// 常量定义
const int _ = 100007, __ = 500007;

int n, qn, tims[_] = {0}, opt[__] = {0}, opa[__] = {0}, opb[__] = {0};

namespace thedick {  // 树链剖分部分
    vector<int> e[_], ce[_];
    
    // 添加边
    inline void adde(int a, int b) {
        e[a].emplace_back(b);
    }
    inline void addde(int a, int b) {
        adde(a, b), adde(b, a);
    }

    // 并查集
    int bfa[_];
    int findbfa(int x) {
        return bfa[x] == x ? x : bfa[x] = findbfa(bfa[x]);
    }
    void linka(int a, int b) {
        bfa[findbfa(b)] = findbfa(a);
    }

    // 树链剖分相关数组
    int dwn[_] = {0};        // 下方关键节点
    int fa[_] = {0};         // 父节点
    int dep[_] = {0};        // 深度
    int dfn[_] = {0};        // DFS序
    int ndf[_] = {0};        // 子树DFS序结束
    int dcnt = 0;            // DFS计数器
    int sz[_] = {0};         // 子树大小
    int mxch[_] = {0};       // 重儿子
    int stk[_] = {0};        // 栈
    int scnt = 0;            // 栈大小

    // DFS进行树链剖分
    void dfs(int x, int ff) {
        fa[x] = ff, dep[x] = dep[ff] + 1;
        dfn[x] = ++dcnt, sz[x] = 1, mxch[x] = 0;

        // 维护栈，计算dwn数组
        while (scnt > 0 && tims[stk[scnt]] >= tims[x])
            dwn[stk[scnt]] = x, scnt--;

        stk[++scnt] = x;

        // 递归处理子节点
        for (auto b : ce[x]) {
            if (b == ff) continue;
            dfs(b, x);
            sz[x] += sz[b];
            if (sz[mxch[x]] < sz[b])
                mxch[x] = b;
        }
        ndf[x] = dcnt;
    }

    int top[_] = {0};  // 链顶

    // 第二次DFS确定重链
    void dfs2(int x, int tp) {
        top[x] = tp;
        if (mxch[x]) dfs2(mxch[x], tp);
        for (auto b : ce[x])
            if (b != fa[x] && b != mxch[x])
                dfs2(b, b);
    }

    // 求LCA
    int lca(int a, int b) {
        while (top[a] != top[b]) {
            if (dep[top[a]] < dep[top[b]]) swap(a, b);
            a = fa[top[a]];
        }
        if (dep[a] > dep[b]) swap(a, b);
        return a;
    }

    // 求a在b方向上的直接子节点
    int lasch(int a, int b) {
        while (top[a] != top[b]) {
            a = top[a];
            if (fa[a] == b) return a;
            a = fa[a];
        }
        return mxch[b];
    }

    int lbw[_] = {0};  // 下方边界

    // 构建树结构
    void makedick() {
        for (int i = 1; i <= n; i++)
            bfa[i] = i, sort(e[i].begin(), e[i].end(), greater<int>());

        // 构建压缩树
        for (int i = 1; i <= n; i++)
            for (auto b : e[i])
                if (i > findbfa(b))
                    ce[i].emplace_back(findbfa(b)), linka(i, b);

        dfs(n, 0), dfs2(n, n);

        // 计算lbw数组
        for (int i = 1; i <= n; i++)
            for (auto b : e[i])
                if (i > b)
                    lbw[lasch(b, i)] = b;
    }

    // 检查a是否是b的祖先
    int chua(int a, int b) {
        if (!a || !b || a == b) return 0;
        int x = lbw[*(--upper_bound(ce[b].begin(), ce[b].end(), a, 
            [](int a, int b) { return dfn[a] < dfn[b]; }))];
        return dfn[a] <= dfn[x] && dfn[x] <= ndf[a];
    }
}

namespace thefuck {  // LCT部分
    int fa[_] = {0};          // 父节点
    int ch[_][2] = {0};       // 左右儿子
    int val[_] = {0};         // 节点值
    int sval[_] = {0};        // 子树和

    // Splay树操作
    inline int isrt(int x) {
        return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
    }
    inline int numch(int x) {
        return ch[fa[x]][1] == x;
    }

    // 更新节点信息
    void up(int x) {
        sval[x] = sval[ch[x][0]] + val[x] + sval[ch[x][1]];
    }

    // 旋转操作
    void roll(int x) {
        int y = fa[x], z = fa[y], o = numch(x);
        if (!isrt(y)) ch[z][numch(y)] = x;
        fa[x] = z, ch[y][o] = ch[x][o ^ 1];
        if (ch[y][o]) fa[ch[y][o]] = y;
        ch[x][o ^ 1] = y, fa[y] = x;
        up(y), up(x);
    }

    // Splay操作
    void splay(int a) {
        while (!isrt(a)) {
            int b = fa[a];
            if (!isrt(b)) roll((numch(a)^numch(b)) ? a : b);
            roll(a);
        }
    }

    // Access操作：将x到根的路径变为偏爱路径
    void bash(int x) {
        for (int i = 0; x; i = x, x = fa[x])
            splay(x), ch[x][1] = i, up(x);
    }

    // 将x变为树根
    int mktp(int x) {
        splay(x);
        if (!ch[x][0]) return fa[x];
        x = ch[x][0];
        while (ch[x][1]) x = ch[x][1];
        splay(x), ch[x][1] = 0, up(x);
        return x;
    }

    // 找子树最左节点
    int ll(int x) {
        splay(x);
        while (ch[x][0]) x = ch[x][0];
        return x;
    }

    // 找子树最右节点
    int rr(int x) {
        splay(x);
        while (ch[x][1]) x = ch[x][1];
        return x;
    }

    // 修改节点值
    void change(int x, int d) {
        splay(x), val[x] = d, up(x);
    }

    int zo[_] = {0}, cfa[_] = {0};  // 辅助数组

    // 添加边操作
    void add(int a, int b) {
        if (a > b) {
            // 简单情况：直接连接
            fa[b] = cfa[b] = a, val[b] = 1, up(b);
            return;
        }

        // 复杂情况：需要调整树结构
        int x = thedick::dwn[b], y = mktp(x), now = a;
        if (zo[y] == x) zo[y] = b;
        if (y) zo[b] = x;

        change(b, val[x]), change(x, y == 0);
        fa[b] = y, fa[x] = b;

        int c = 0, d = 0;

        // 向上调整树结构
        while (a) {
            splay(a), ch[a][1] = c, up(a);
            
            if (sval[a]) {
                x = a;
                // 找到需要调整的节点
                while (1) {
                    if (sval[ch[x][1]]) x = ch[x][1];
                    else if (val[x]) break;
                    else x = ch[x][0];
                }

                if (x > b) break;
                y = mktp(x);
                if (y > b) break;

                splay(now), ch[now][1] = 0;
                if (zo[now]) splay(zo[now]), fa[zo[now]] = y, change(zo[now], 1), zo[now] = 0;

                a = now = cfa[x], change(x, 0);
                x = rr(x), splay(x);
                if (d) fa[d] = x, zo[x] = ch[x][1] = ll(d);
                d = x, c = 0;
            } else {
                c = a, a = fa[a];
            }
        }

        cfa[b] = cfa[thedick::dwn[b]], cfa[thedick::dwn[b]] = b;
        if (d) d = ll(d), change(d, 1), fa[d] = b;

        bash(1), splay(1);
    }

    // 计算路径信息
    pair<int, int> make(int a, int b) {
        if (!a || !b || a == b) return make_pair(0, 0);

        bash(a), splay(a);
        int aa = a, c;

        // 在Splay树中查找
        while (a) {
            if (a < b) c = a, a = ch[a][0];
            else a = ch[a][1];
        }

        splay(c), a = ch[c][1];
        if (!sval[a]) return make_pair(1, aa);

        int temp = sval[a];
        while (1) {
            if (sval[ch[a][0]]) a = ch[a][0];
            else if (!val[a]) c = a, a = ch[a][1];
            else {
                if (ch[a][0]) {
                    a = ch[a][0];
                    while (ch[a][1]) a = ch[a][1];
                    c = a;
                }
                break;
            }
        }

        return make_pair(temp + 1, c);
    }

    // 主查询函数
    int fuck(int a, int b) {
        if (a == b) return 0;
        if (a > b) swap(a, b);

        int c = thedick::lca(a, b);
        pair<int, int> x = make(a, c);
        
        if (b == c) return x.first + (!thedick::chua(x.second, c));

        pair<int, int> y = make(b, c);
        return x.first + y.first + (!thedick::chua(x.second, c) || !thedick::chua(y.second, c));
    }
}

int main() {
    ios::sync_with_stdio(0), cout.tie(nullptr);

    n = 0;
    ty(), qn = ty();
    tims[1] = 0;

    // 读入所有操作
    for (int i = 1; i <= qn; i++) {
        opt[i] = ty(), opa[i] = ty(), opb[i] = ty();
        n = max(n, max(opa[i], opb[i]));
        if (opt[i] == 1)
            thedick::addde(opa[i], opb[i]), tims[opb[i]] = i;
    }

    // 预处理
    thedick::makedick();

    // 处理操作
    for (int i = 1; i <= qn; i++) {
        if (opt[i] == 1)
            thefuck::add(opa[i], opb[i]);
        if (opt[i] == 2)
            cout << thefuck::fuck(opa[i], opb[i]) << '\n';
    }

    return 0;
}

算法核心要点详解

1. 谷图性质分析

在谷图 G(T) 中，两个节点能直接跳跃的条件是它们路径上的所有中间节点编号都 ≤ min(u,v)。这意味着：

• 从小编号向大编号跳跃相对容易
• 从大编号向小编号跳跃受到更多限制

2. 树链剖分的作用

• 预处理LCA：快速求任意两点最近公共祖先
• 路径分解：将任意路径分解为若干重链
• 维护dwn数组：记录每个节点下方的重要节点

3. LCT的动态维护

LCT用于动态维护谷图的连通性：

• Access操作：暴露路径
• Splay操作：调整树结构
• 维护sval：记录子树中可跳跃的节点信息

4. 查询处理策略

对于查询 u→v：

1. 找到LCA c
2. 分别计算 u→c 和 v→c 在谷图中的跳跃次数
3. 考虑在LCA处是否能直接跳跃

复杂度分析

• 预处理：O(n log n)
• 每次操作：O(log n) 均摊
• 总复杂度：O((n+q) log n)

总结

这道题综合运用了：

1. 树链剖分 处理静态树信息
2. Link-Cut Tree 动态维护树结构
3. 谷图性质分析 转化问题
4. 复杂的状态维护 处理跳跃关系

是一个很好的高级数据结构综合题目，考察了对LCT和树链剖分的深入理解。