[ABC368D] Minimum Steiner Tree题解

· · 题解

题解

题目传送门

分析

要解决这题，我们可以用一个数组 cntp 用来计数每一棵子树里有几个节点属于 V，如果 cntp_i=0，那么在这颗子树里一个也不用选，如果 cntp_i=K，这棵树的部分就可能作为答案。

我们再用一个数组 cnt 统计在每一颗子树里至少要选择的节点个数，由上面的分析，当 cntp_i=0 时，cnt_i 应该赋值为 0。否则，cnt_i=\sum_{i=1}^m cnt_{v_i}，其中 v_1,v_2,\dots,v_m 为节点 i 的子节点。

最后统计答案时，只要统计满足 cntp_i=K 的所有 i 中 cnt_i 的最小值即可。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n,k,v[N],p[N],d[N];
vector<int> es[N];
bool flag[N],points[N],vst[N];
int cnt[N],cntp[N];
void dfs(int u,int fa)
{
    p[u] = fa; d[u] = d[fa] + 1; cntp[u] = points[u];
    for(int i = 0,v;i < es[u].size();i++)
    {
        v = es[u][i];
        if(v == fa) continue;
        dfs(v,u);
        cntp[u] += cntp[v];
    }
}
int search(int u)
{
    if(vst[u])  return cnt[u];
    vst[u] = true;
    if(es[u].size() == 1 && es[u][0] == p[u])   return cnt[u] = points[u];
    if(cntp[u] == 0)    return cnt[u] = 0;
    int sum = 1;
    for(int i = 0,v;i < es[u].size();i++)
    {
        v = es[u][i];
        if(v == p[u])   continue;
        sum += search(v);
    }
    return cnt[u] = sum;
}
void solve()
{
    cin >> n >> k;
    for(int i = 1,u,v;i < n;i++) { cin >> u >> v; es[u].push_back(v); es[v].push_back(u); }
    for(int i = 1;i <= k;i++)   cin >> v[i],points[v[i]] = true;
    dfs(1,0);
    search(1);
    int minn = n;
    for(int i = 1;i <= n;i++)
        if(cntp[i] == k)    minn = min(minn,cnt[i]);
    cout << minn << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
//  cin >> T;
    while(T--) solve();
    return 0;
}

Atcoder提交记录