最短路

题目大意

存在 $n$ 个节点 ，$m$ 次操作，每次操作或者查询两个节点之间的距离，或者删除一个节点，并且删除一个点，并让其邻域的点两两之间连上一条边。

题解思路

题目分析

我们可以将删除操作的本质理解为：对于所有经过该节点的最短路径，其距离长度将减少 $1$。基于这一观察，可以将问题转化为以下形式：

初始状态下，所有节点的权值均为 $1$。操作1对应将指定节点的权值修改为 $0$，而操作2则转化为查询两个节点之间最短路径上权值为 $1$ 的节点数量。

这种转化使得问题可以通过树链剖分技术高效解决。具体而言，我们可以：

1. 建立树链剖分数据结构来维护节点权值
2. 实现单点修改操作（将节点权值从1改为0）
3. 通过路径查询统计两个节点间最短路径上权值为1的节点数量

时间复杂度 O($n\log^2 n$)

参考代码

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

class Tree {
    int n;
    vector<int> dfn, top, fa, son, sz, dep, ys;
    vector<vector<int> > edge;
    vector<int> fiw;
    int tot = 0;

public:
    int lowbit(int x) {
        return x & -x;
    }

    void modify(int x, int y) {
        while (x <= n) {
            fiw[x] += y;
            x += lowbit(x);
        }
    }

    int query(int x) {
        int sums = 0;
        while (x) {
            sums += fiw[x];
            x -= lowbit(x);
        }
        return sums;
    }

    int sum(int l, int r) {
        return query(r) - query(l - 1);
    }

    Tree(int n) : dfn(n + 1), top(n + 1), fa(n + 1), son(n + 1), sz(n + 1), dep(n + 1), ys(n + 1), fiw(n + 1, 1),
                  edge(n + 1), n(n) {
        for (int i = 1; i <= n; i++) {
            if (i + lowbit(i) <= n) fiw[i + lowbit(i)] += fiw[i];
        }
    }

    void add_edge(int x, int y) {
        edge[x].emplace_back(y);
        edge[y].emplace_back(x);
    }

    void dfs1(int u, int p) {
        sz[u] = 1;
        fa[u] = p;
        dep[u] = dep[p] + 1;
        for (auto i: edge[u]) {
            if (i == p) continue;
            dfs1(i, u);
            sz[u] += sz[i];
            if (sz[son[u]] < sz[i]) son[u] = i;
        }
    }

    void dfs2(int u, int t) {
        dfn[u] = ++tot;
        ys[tot] = u;
        top[u] = t;
        if (son[u]) {
            dfs2(son[u], t);
        }
        for (auto i: edge[u]) {
            if (i == fa[u] || i == son[u])continue;
            dfs2(i, i);
        }
    }

    void init() {
        dfs1(1, 0);
        dfs2(1, 1);
    }

    void delete_node(int q) {
        modify(dfn[q], -1);
    }

    int lca(int u, int v) {
        int _sums = 0;
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            _sums += sum(dfn[top[u]], dfn[u]);
            u = fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        _sums += sum(dfn[u], dfn[v]);
        return _sums;
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    Tree tree(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree.add_edge(u, v);
    }
    tree.init();
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            tree.delete_node(x);
        } else {
            int u, v;
            cin >> u >> v;
            cout << tree.lca(u, v) - 1 << endl;
        }
    }
}