Problem - 1029E - Codeforces

题意

给定一棵 $n$ 个节点的无根树）。你可以执行任意次操作：在根节点（1 号点）与任意其他节点之间添加一条边。

求最少需要添加多少条边，才能使得根节点到树上所有节点的距离都不超过 2。

思路

如果直接去想“怎么连边最优”，情况会非常复杂。

换个思路，你想啊，我们在 1 和 $u$ 之间连一条边，$u$ 到根的距离就变成了 1，那 $u$ 的儿子们到根的距离自然就变成 2 了。

也就是说：我们选一个点 $u$ 连边，它自己和它的直接儿子们就全部被“覆盖”了（距离 $\le 2$）。

树形 DP 状态设计

那么我们根据一个节点 $u$ 的覆盖来源，定义三个状态：

  • f[u][0]：点 $u$ 被自己覆盖（自己选了）。

  • f[u][1]：点 $u$ 被儿子覆盖（自己不选，指望至少一个儿子选）。

  • f[u][2]：点 $u$ 被父亲覆盖（自己不选，儿子也不选，只能指望爹）。

转移方程

1. 当节点 $u$ 放置物品时（求 $f[u][0]$）：
既然 $u$ 已经放置了物品，那么它的所有儿子 $v$ 是否放置物品、是否被覆盖都无关紧要（即儿子可以处于任意状态）。为了求最小代价，我们取儿子三个状态中的最小值。

$$f[u][0] = cost(u) + \sum_{v \in son(u)} \min(f[v][0], f[v][1], f[v][2])$$

(注：代码中 $cost(u)$ 的初始化由深度 $d$ 决定,$d$>1的时候为1)

2. 当节点 $u$ 被父亲覆盖时（求 $f[u][2]$）：

此时 $u$ 自身不放置物品，因此儿子 $v$ 不能指望被 $u$ 覆盖。儿子 $v$ 只能靠自己（$f[v][0]$）或者靠 $v$ 的儿子（$f[v][1]$）。

$$f[u][2] = \sum_{v \in son(u)} \min(f[v][0], f[v][1])$$

3. 当节点 $u$ 被儿子覆盖时（求 $f[u][1]$）：

此时 $u$ 本身不放置物品，所有的儿子 $v$ 也必须被覆盖，所以儿子们同样只能在 $f[v][0]$ 和 $f[v][1]$ 中选择。

$$f[u][1]{初始} = \sum{v \in son(u)} \min(f[v][0], f[v][1])$$

关键细节：状态 $f[u][1]$ 的前提是必须至少有一个儿子放置了物品。

  • 如果我们按上述贪心取最小时，已经有至少一个儿子满足 $f[v][0] \le f[v][1]$，说明自然而然就选了至少一个儿子放置物品，那么直接累加即可（代码中使用 ok = 1 标记）。

  • 如果所有儿子都是 $f[v][1] < f[v][0]$，说明贪心策略下没有一个儿子放置了物品，这不符合 $f[u][1]$ 的定义。此时，我们必须强行让其中一个儿子改变主意，选择 $f[v][0]$。为了让代价增加得最少，我们应当找到差值 $(f[v][0] - f[v][1])$ 最小的那个儿子强制覆盖。

分块代码

看完思路后，我们一步一步来分块拆解代码。

1. DFS 初始化与深度判断

这里是把边界条件融进 DP 的关键，把深度 $d > 1$ 时的代价设为 1，其他的白嫖。

1
2
3
4
void dfs(int u,int p,int d){
    if(d>1) f[u][0]=1; // 只有深度>1的点连边才有真实代价
    f[u][1]=0,f[u][2]=0;
    ll mi=1e9,ok=0;   // mi 用来记最小的反悔代价，ok 标记有没有儿子主动选了自己

2. 状态转移与强制“至少一个”

遍历子树转移状态，尤其是对 f[u][1] 的修正处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int v:adj[u]){
	if(v==p) continue;
	dfs(v,u,d+1);
	
	// 状态 0：自己选了，儿子随意
	f[u][0]+=min({f[v][0],f[v][1],f[v][2]});
	
	// 状态 2：自己指望爹，儿子不能指望爹
	f[u][2]+=min(f[v][1],f[v][0]);
	
	// 状态 1：必须至少有一个儿子靠自己
	if(f[v][0]<f[v][1]) {
		ok=1; 
		f[u][1]+=f[v][0]; // 儿子主动选 0 更优，打上 ok 标记
	} else {
		f[u][1]+=f[v][1]; // 儿子选 1 更优
		mi=min(mi,f[v][0]-f[v][1]); // 记录如果强迫这个儿子选 0 需要多掏多少代价
	}
}
// 如果没有任何儿子主动选 0，强行加上最小的差值，逼迫一个选 0
if(!ok) f[u][1]+=mi;

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
vector<int> adj[maxn];
ll f[maxn][3];
int n;
void dfs(int u,int p,int d){
    if(d>1) f[u][0]=1;
    f[u][1]=0,f[u][2]=0;
    ll mi=1e9,ok=0;
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u,d+1);
        f[u][0]+=min({f[v][0],f[v][1],f[v][2]});
        f[u][2]+=min(f[v][1],f[v][0]);
        if(f[v][0]<f[v][1]) {
            ok=1,f[u][1]+=f[v][0];
        }else {
            f[u][1]+=f[v][1];
            mi=min(mi,f[v][0]-f[v][1]);
        }
    }
    if(!ok) f[u][1]+=mi;
}
void solve()
{
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0,0);
    cout<<min({f[1][0],f[1][1],f[1][2]})<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ___T=1;
    //cin>>___T;
    while(___T--)  solve();
    return 0;
}

后记

我是专门学习树形DP然后找到的题目，看了题解发现还有贪心的写法
先看代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
vector<int> adj[maxn];
int dep[maxn],fa[maxn];
int n;
void dfs(int u,int p){
    dep[u]=dep[p]+1;
    fa[u]=p;
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
    }
}
int vis[maxn];
void solve()
{
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    priority_queue<pair<int,int> > pq;
    for(int i=1;i<=n;++i){
        if(dep[i]>3) pq.push({dep[i],i});
        //cout<<dep[i]<<" "<<i<<"\n";
    }
    int ans=0;
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(vis[u]) continue;
        u=fa[u];// 贪心策略：把连边机会给父亲
        //cout<<u<<"\n";
        vis[u]=1;// 父亲自己被覆盖了
        ans++;// 连了一条边
        for(int v:adj[u]){
            vis[v]=1;// 父亲的所有邻居（包括最开始那个最深的儿子、其他的儿子、爷爷）统统被覆盖
        }
    }
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ___T=1;
    //cin>>___T;
    while(___T--)  solve();
    return 0;
}

Why这个贪心是对的？

贪心的核心思想就是：“从最底层开始，每次把好钢用在刀刃上。”

  1. 为什么要找最深的未覆盖节点？

    因为最深的节点“最危险”。如果不先管最底层的节点，而去管上面的节点，上面的节点虽然能覆盖一片，但不一定够得着最底层的这个节点。

  2. 找到了最深的未覆盖节点 $x$ 后，连边连在哪里收益最大？

    由于 $x$ 是当前最深的未覆盖节点，说明它的子节点要么没有，要么已经被覆盖过了。

    为了覆盖 $x$，我们有三种连边选择：

    • 连在 $x$ 的子节点上：纯属浪费，因为子节点已经被覆盖了。

    • 连在 $x$ 自己身上：能覆盖 $x$ 的儿子、$x$ 自己、$x$ 的父亲。

    • 连在 $x$ 的父亲身上：能覆盖 $x$ 自己、$x$ 的兄弟们、$x$ 的父亲、$x$ 的爷爷！

    显然，连在 $x$ 的父亲身上血赚！ 它不仅解决了当前最深节点 $x$ 的覆盖问题，还能顺手救下一大批更上层的节点。这也就是代码中 u = fa[u] 这一步的灵魂所在。