A28309. 割裂
填空题
困难
知识点
题目描述
割裂
题目描述
小杨有一棵包含 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 >。
输出格式
输出一个正整数，代表能够删除的节点个数。
样例
输入样例
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6输出样例
2参考答案
#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();
}
上一题
下一题