题解

#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);
}

// 树链划分预处理
dfs1(1, 0, 1); // 第一遍DFS（根节点深度为1）
cnt = 0; // 重置DFS序计数器
dfs2(1, 1); // 第二遍DFS（根节点作为重链起点）

// 初始化树状数组和删除标记
memset(Shuzhuang, 0, sizeof(Shuzhuang));
memset(ShanChu, 0, sizeof(ShanChu));

// 处理操作指令
while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 1) { // 节点删除操作
        int x;
        scanf("%d", &x);
        if (!ShanChu[x]) {
            ShanChu[x] = true;
            // 在树状数组中标记删除
            Shu_Update(XuHao[x], 1);
        }
    } else { // 最短路径查询
        int x, y;
        scanf("%d%d", &x, &y);
        // 步骤1：计算原始树上的距离
        int l = lca(x, y);
        int yuanJu = Shen[x] + Shen[y] - 2 * Shen[l];

        // 步骤2：计算路径上被删除的节点数
        int shanCnt = nb_cnt(x, y);

        // 步骤3：输出最终路径长度
        // （每个被删节点会使路径长度减少1）
        printf("%d\n", yuanJu - shanCnt);
    }
}

return 0;

}