简答题 偏难
#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>。

【输出描述】

输出一个正整数,代表能够删除的节点个数。

【样例输入】

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6

【样例输出】

2

【数据范围】

对于全部数据,保证有 。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e6+10; int n, k; vector&lt;int&gt; 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 &lt;= 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] &lt; dep[v]) swap(u, v);     int t = dep[u] - dep[v];     for(int i = 0; i &lt;= 20; i++) {         if(t &amp; (1 &lt;&lt; i)) u = f[u][i];     }     for(int i = 20; i &gt;= 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] &amp;&amp; h[u]) {         ans++;     } } void solve() {     cin &gt;&gt; n &gt;&gt; k;     for(int i = 1; i &lt; n; i++) {         int u, v;         cin &gt;&gt; u &gt;&gt; v;         e[u].push_back(v);         e[v].push_back(u);     }     dfs(1, 0);     for(int i = 1; i &lt;= k; i++) {         int u, v;         cin &gt;&gt; u &gt;&gt; v;         int lc = lca(u, v);         g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;     }     int u, v;     cin &gt;&gt; u &gt;&gt; v;     int lc = lca(u, v);     h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;     dfs2(1, 0);     cout &lt;&lt; ans &lt;&lt; '\n'; } int main() {     solve(); }</pre>
这道题暂未补解析。