最短路 题目大意 存在 nnn 个节点 ，mmm 次操作，每次操作或者查询两个节点之间的距离，或者删除一个节点，并且删除一个点，并让其邻域的点两两之间连上一条边。 题解思路 题目分析 我们可以将删除操作的本质理解为：对于所有经过该节点的最短路径，其距离长度将减少 111。基于这一观察，可以将问题转化为以下形式： 初始状态下，所有节点的权值均为 111。操作1对应将指定节点的权值修改为 000，而操作2则转化为查询两个节点之间最短路径上权值为 111 的节点数量。 这种转化使得问题可以通过树链剖分技术高效解决。具体而言，我们可以： 1. 建立树链剖分数据结构来维护节点权值 2. 实现单点修改操作（将节点权值从1改为0） 3. 通过路径查询统计两个节点间最短路径上权值为1的节点数量 时间复杂度 O(nlog⁡2nn\log^2 nnlog2n) 参考代码

#include <bits/stdc++.h> using namespace std; const int N = 100005; // g: 树的邻接表存储 vector<int> g[N]; // n: 节点数, m: 操作次数, cnt: DFS序计数器 int n, m, cnt; // Fu: 父节点, Shen: 节点深度, DaXiao: 子树大小, ZhongEr: 重儿子 int Fu[N], Shen[N], DaXiao[N], ZhongEr[N]; // DingDian: 节点所在重链的顶端, XuHao: 节点的DFS序号 int DingDian[N], XuHao[N]; // Shuzhuang: 树状数组（记录被删除的节点） int Shuzhuang[N]; // ShanChu: 标记节点是否被删除 bool ShanChu[N]; // 树状数组更新函数：在位置pos添加值val void Shu_Update(int pos, int val) { for (; pos <= n; pos += (pos & -pos)) Shuzhuang[pos] += val; } // 树状数组查询函数：[1, pos]区间和 int Shu_Query(int pos) { int res = 0; for (; pos; pos -= (pos & -pos)) res += Shuzhuang[pos]; return res; } // 查询区间[L, R]的和（自动处理L>R的情况） int QuJian_Query(int L, int R) { if (L > R) swap(L, R); return Shu_Query(R) - Shu_Query(L - 1); } // 第一遍DFS：计算父节点、深度、子树大小、重儿子 void dfs1(int u, int fu, int deep) { Shen[u] = deep; Fu[u] = fu; DaXiao[u] = 1; ZhongEr[u] = 0; // 初始化重儿子 for (int v : g[u]) { if (v == fu) continue; dfs1(v, u, deep + 1); DaXiao[u] += DaXiao[v]; // 更新重儿子（子树最大的子节点） if (DaXiao[v] > DaXiao[ZhongEr[u]]) ZhongEr[u] = v; } } // 第二遍DFS：确定DFS序和重链顶端 void dfs2(int u, int ding) { DingDian[u] = ding; XuHao[u] = ++cnt; // 分配DFS序号 if (!ZhongEr[u]) return; // 叶子节点直接返回 // 优先遍历重儿子（保持重链连续） dfs2(ZhongEr[u], ding); // 遍历轻儿子（开启新重链） for (int v : g[u]) { if (v == Fu[u] || v == ZhongEr[u]) continue; dfs2(v, v); } } // 求节点u和v的最近公共祖先（LCA） int lca(int u, int v) { // 当不在同一重链时交替上跳 while (DingDian[u] != DingDian[v]) { if (Shen[DingDian[u]] < Shen[DingDian[v]]) swap(u, v); u = Fu[DingDian[u]]; } // 返回深度较小的节点（即LCA） return Shen[u] < Shen[v] ? u : v; } // 查询u->v路径上被删除的节点数量 int nb_cnt(int u, int v) { int res = 0; while (DingDian[u] != DingDian[v]) { if (Shen[DingDian[u]] < Shen[DingDian[v]]) swap(u, v); // 查询当前重链区间 res += QuJian_Query(XuHao[DingDian[u]], XuHao[u]); u = Fu[DingDian[u]]; // 跳转到父链 } // 最后一条重链的查询 if (Shen[u] > Shen[v]) swap(u, v); res += QuJian_Query(XuHao[u], XuHao[v]); return res; } int main() { // 数据读入 scanf("%d%d", &n, &m); // 构建初始树 for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } }