简答题
偏难
#20403
割裂 时间限制:1 s,内存限制:512 MB 【问题描述】 小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。 小杨设置了 a 个好点对 {<u…
割裂
时间限制:1 s,内存限制:512 MB
【问题描述】
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。
小杨设置了 a 个好点对 {<u1,v1>、<u2,v2>、……、<ua,va>} 和 1 个坏点对 {<bu,bv>}。一个节点能够被删除,当且仅当:
◆ 删除该节点后对于所有的 i(1<=i<=a),好点对 ui 和 vi 仍然连通;
◆ 删除该节点后坏点对 bu 和 bv 不连通。
如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,有多少个节点能够被删除。
【输入描述】
第一行包含两个正整数 n、a,含义如题面所示。
之后 n - 1 行,每行包含两个正整数 xi、yi,代表存在一条连接节点 xi 和 yi 的边。
之后 a 行,每行包含两个正整数 ui、vi,代表一个好点对 <ui,vi>。
最后一行包含两个正整数 bu、bv,代表坏点对 <bu,bv>。
【输出描述】
输出一个正整数,代表能够删除的节点个数。
【样例输入】
【样例输出】
【数据范围】
对于全部数据,保证有 。

![]()
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
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);
}
}
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];
}
if(u == v) return u;
return f[u][0];
}
int ans;
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];
}
if(!g[u] && h[u]) {
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]--, g[f[lc][0]]--;
}
int u, v;
cin >> u >> v;
int lc = lca(u, v);
h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
dfs2(1, 0);
cout << ans << '\n';
}
int main() {
solve();
}</pre>
这道题暂未补解析。