试一试
2025-09-13 10:34:25
发布于：浙江
12阅读
0回复
0点赞
4120：【GESP2503八级】割裂
时间限制: 4000 ms 内存限制: 524288 KB
提交数: 148 通过数: 17
【题目描述】
小杨有一棵包含n
个节点的树，其中节点的编号从1
到n
。
小杨设置了a
个好点对{<u1,v1>,<u2,v2>,...,<ua,va>}
和1
个坏点对<bu,bv>
。一个节点能够被删除，当且仅当：
(1)删除该节点后对于所有的i
(1≤i≤a
)，好点对ui
和vi
仍然连通；
(2)删除该节点后坏点对 和 不连通。
如果点对中的任意一个节点被删除，其视为不连通。
小杨想知道，有多少个节点能够被删除。
【输入】
第一行包含两个正整数n,a
，含义如题面所示。
之后n−1
行，每行包含两个正整数xi,yi
，代表存在一条连接节点xi
和yi
的边。
之后a
行，每行包含两个正整数ui,vi
，代表一个好点对<ui,vi>
。
最后一行包含两个正整数bu,bv
，代表坏点对<bu,bv>
。
【输出】
输出一个正整数，代表能够删除的节点个数。
【输入样例】
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
【输出样例】
2
【提示】
数据范围
对于20%的数据，n≤10
,a=0
;
对于20%的数据，n≤100
,a≤100
;
对于60%的数据，n≤106
,a≤105
;
对于全部数据，保证1≤n≤106
，0≤a≤105
，ui≠vi
，bu≠bv
。
全部评论 2
#include<iostream> #include<vector> using namespace std; const int N = 1e6 + 10; int n, q, u, v, a[N], fa[N][20], dep[N], cnt; vector<int> g[N]; void dfs(int u, int f){ fa[u][0] = f; dep[u] = dep[f] + 1; for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for(int v: g[u]){ if(v == f) continue; dfs(v, u); } } int lca(int u, int v){ if(dep[u] < dep[v]) swap(u, v); for(int i = 19; i >= 0; i--){ if((dep[u] - dep[v]) & (1 << i)) u = fa[u][i]; } if(u == v) return u; for(int i = 19; i >= 0; i--){ if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; } return fa[u][0]; } void get_ans(int u, int f){ for(int v: g[u]){ if(v == f) continue; get_ans(v, u); a[u] += a[v]; } } int main(){ cin >> n >> q; for(int i = 1; i < n; i++){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); while(q--){ cin >> u >> v; int w = lca(u, v); a[u]++; a[v]++; a[w]--; a[fa[w][0]]--; } get_ans(1, 0); cin >> u >> v; int w = lca(u, v); while(u != w){ if(a[u] == 0) cnt++; u = fa[u][0]; } while(v != w){ if(a[v] == 0) cnt++; v = fa[v][0]; } if(a[u] == 0) cnt++; cout << cnt; return 0; }2025-09-14 来自 福建
0
有帮助，赞一个