解题思路
问题分析
我们需要找到满足以下条件的节点：
-
删除该节点后，所有好点对仍然连通
-
删除该节点后，坏点对不连通
关键思路
-
好点对连通性分析：
-
如果一个节点在某个好点对的路径上，删除它会导致该好点对不连通
-
因此，能被删除的节点不能在任何好点对的路径上
-
使用树上差分标记所有好点对路径上的节点
-
-
坏点对连通性分析：
-
删除节点后坏点对要不连通，说明该节点必须在坏点对的路径上
-
因此，能被删除的节点必须在坏点对的路径上
-
-
综合条件：
-
节点必须在坏点对路径上
-
节点不能在任何一个好点对路径上
-
算法步骤
-
构建树并预处理LCA
-
使用树上差分标记所有好点对路径上的节点
-
遍历坏点对路径，统计满足条件的节点
代码注释
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; const int N = 1e6 + 10,inf = 0x3f3f3f3f; vector<int> g[N]; // 邻接表存储树 int n,m; // n:节点数, m:好点对数量 int s[N]; // 备用数组 vector<pii> a; // 存储好点对 int vis[N]; // 备用标记数组 int f[N][25],dep[N]; // f:倍增数组, dep:节点深度 int b1,b2; // 坏点对的两个节点 int ans; // 答案：满足条件的节点数 int d[N]; // 差分数组，标记好点对路径上的节点// DFS预处理LCA和深度 void dfs(int x,int fa) {f[x][0] = fa; // 直接父节点dep[x] = dep[fa] + 1; // 深度为父节点深度+1// 预处理倍增数组for(int i = 1; i <= 20; i++){int y = f[x][i - 1];f[x][i] = f[y][i - 1];}// 递归处理子节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(y == fa) continue;dfs(y,x);} }// DFS计算差分数组的前缀和 void dfs2(int x,int fa) {for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(y == fa) continue;dfs2(y,x);d[x] += d[y]; // 子节点的值累加到父节点 } }// 求两个节点的最近公共祖先(LCA) int lca(int x,int y) {// 确保x是深度较大的节点if(dep[x] < dep[y]) swap(x,y);// 将x提升到与y同一深度for(int i = 20; i >= 0; i--){int fa = f[x][i];if(dep[fa] >= dep[y]){x = fa;}} if(x == y) return x; // 如果相等，y就是LCA// 同时提升x和y直到它们的父节点相同for(int i = 20; i >= 0; i--){int fx = f[x][i],fy = f[y][i];if(fx != fy){x = fx,y = fy;}}return f[x][0]; // 返回LCA }int main() {cin >> n >> m;// 读入树结构for(int i = 1; i < n; i++){int x,y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}// 预处理LCAdfs(1,0);// 处理所有好点对for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;int rt = lca(x,y); // 求好点对的LCA// 树上差分标记好点对路径上的节点// 在x和y处+1，在LCA处-1，在LCA的父节点处-1d[x]++,d[y]++,d[rt]--,d[f[rt][0]]--;}// 计算差分数组的前缀和，d[x] > 0 表示节点x在某个好点对的路径上dfs2(1,0);// 读入坏点对cin >> b1 >> b2;int rt = lca(b1,b2); // 坏点对的LCA// 遍历坏点对路径，统计满足条件的节点// 条件：在坏点对路径上(d[节点] == 0)且不在任何好点对路径上while(b1 != rt){if(d[b1] == 0) ans++; // 不在好点对路径上b1 = f[b1][0]; // 向LCA移动 }while(b2 != rt){if(d[b2] == 0) ans++; // 不在好点对路径上b2 = f[b2][0]; // 向LCA移动 }if(d[rt] == 0) ans++; // 检查LCA本身 cout << ans;return 0; }