GESP2025年3月认证C++八级( 第三部分编程题（2）割裂）

参考程序：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;int n, k;                  // n: 节点数，k: 好点对数量
vector<int> e[N];          // 邻接表存树
int f[N][25];              // f[u][i] 表示 u 的第 2^i 个祖先
int dep[N];                // dep[u] 表示 u 的深度
int g[N], h[N];            // 差分数组，g 为好路径计数，h 为坏路径计数// 预处理 DFS：记录深度和倍增数组
void dfs(int u, int fa){dep[u] = dep[fa] + 1;f[u][0] = fa;for(int i = 1; i <= 20; i++){f[u][i] = f[f[u][i - 1]][i - 1]; // 倍增构建祖先表}for(auto v: e[u]){if(v == fa) continue;dfs(v, u);}
}// 倍增法求 LCA（最近公共祖先）
int lca(int u, int v){if(dep[u] < dep[v]) swap(u, v);int t = dep[u] - dep[v];for(int i = 0; i <= 20; i++)if(t & (1 << i)) u = f[u][i];for(int i = 20; i >= 0; i--)if(f[u][i] != f[v][i])u = f[u][i], v = f[v][i];return u == v ? u : f[u][0];
}int ans = 0;// 差分 DFS：累加好/坏路径经过的次数
void dfs2(int u, int fa){for(auto v: e[u]){if(v == fa) continue;dfs2(v, u);g[u] += g[v]; // 汇总好路径h[u] += h[v]; // 汇总坏路径}// 删除该点不会破坏任何好路径（即好路径数为 0），// 且能破坏坏路径（即坏路径数不为 0）if(g[u] == 0 && h[u] > 0)ans++;
}void solve(){cin >> n >> k;for(int i = 1; i < n; i++){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1, 0); // 预处理// 构建所有好路径差分for(int i = 1; i <= k; i++){int u, v;cin >> u >> v;int lc = lca(u, v);g[u]++; g[v]++; g[lc] -= 2;}// 构建坏路径差分int u, v;cin >> u >> v;int lc = lca(u, v);h[u]++; h[v]++; h[lc] -= 2;dfs2(1, 0); // 执行差分统计 + 判断可删点cout << ans << '\n';
}int main(){solve();
}