[树形DP] 手机网络
PI_AC
·
·
题解
题目
手机网络
题解
首先我们确定这道题是树形DP，而且可以看出这道题和树的最大独立集有几分相似
那么我们就先打一个树的最大独立集出来，但我们发现这样并不能AC
因为树的最大独立集可以全部由结点的儿子转移过来，而这道题还有另一种可能，就是有结点的父亲转移过来，所以我们不能像最大独立集那样定义状态，我们还需要多定义一个状态
那么我们就可以分情况对这三种状态进行状态转移方程的讨论：
当$j$等于$0$时，因为$i$点有一个通讯塔，所以$son(i)$有可能从它的父亲（也就是$i$点）转移过来，也有可能有它的儿子转移过来，当然，也有可能它自己本身就有一个通讯塔，即
$$dp[i][0]=\sum Min(dp[son(i)][0],dp[son(i)][1],dp[son(i)][2])+1$$
(因为我们在i结点建立了一个通讯塔，所以要加1)
当$j$等于$1$时，因为$i$点没有通讯塔，所以$son(i)$不可能从它的父亲转移过来，它只有可能由它的儿子转移过来，或者是它自己有一个通讯塔，即
$$dp[i][1]=\sum Min(dp[son(i)][0],dp[son(i)][2])$$
当$j$等于$2$时，因为$i$点没有通讯塔，所以$son(i)$也不可能从它的父亲转移过来，它只有可能由它的儿子转移过来，或者是它自己有一个通讯塔，即
$$dp[i][2]=\sum Min(dp[son(i)][0],dp[son(i)][2])$$
但这样写我们很容易发现一个问题，如果$dp[i][2]$全是从$dp[son(i)][2]$转移过来的话，就证明它的所有儿子都没有通讯塔，那么就不可能将它覆盖，如何避免这种情况呢？
其实我们只需要记录下每一次$dp[son(i)][0]-dp[son(i)][2]$的差值，再取一个$min$值，简单的来说，就是
$$p=Min(dp[son(i)][0]-dp[son(i)][2])$$
在最后，如果我们发现$dp[i][2]$全是从$dp[son(i)][2]$转移过来的话，就再加上一个$p$，就相当于将其中的一个$dp[son(i)][2]$强制转换为了$dp[son(i)][0]$，同时还保证了最小
综上所述
$$dp[i][j]=\begin{cases} \sum Min(dp[son(i)][0],dp[son(i)][1],dp[son(i)][2])+1(j==0) \\ \sum Min(dp[son(i)][0], dp[son(i)][2])(j==1) \\ \sum Min(dp[son(i)][0], dp[son(i)][2])(j==2\ and\ flag==1) \\ \sum Min(dp[son(i)][0], dp[son(i)][2])+p(j==2\ and\ flag==0) \end{cases}$$
$flag$表示$dp[i][2]$是否由一个或多个$dp[son(i)][0]$转移过来
值得注意的是，最后输出的是$Min(dp[root][0],dp[root][2])$，因为最后的根结点是不可能有父亲的
----
# 代码
```cpp
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define reg register
template <class T>
inline T read() {
T x = 0; T f = 1; char s = getchar();
while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
while(s >= '0' && s <= '9') {x = (x << 3) + (x << 1) + s - 48; s = getchar();}
return x * f;
}
template <typename T>
inline void wri(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x / 10) wri(x / 10);
putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x, char s) {
wri(x);
putchar(s);
}
template <typename T>
inline T Min(T x, T y) {return x < y ? x : y;}
#define MAXN 10005
#define INF 0x3f3f3f3f
vector <int> G[MAXN];
int n;
int dp[MAXN][3];
bool vis[MAXN];
inline void dfs(int x) {
vis[x] = 1;
bool flag = 0;
int siz = G[x].size(), p = INF;
for(reg int i = 0;i <= siz - 1;i ++)
if(! vis[G[x][i]]) {
dfs(G[x][i]);
dp[x][0] += Min(dp[G[x][i]][0], Min(dp[G[x][i]][1], dp[G[x][i]][2])); //状态转移
dp[x][1] += Min(dp[G[x][i]][0], dp[G[x][i]][2]);
if(dp[G[x][i]][0] <= dp[G[x][i]][2]) {
flag = 1;
dp[x][2] += dp[G[x][i]][0];
}
else {
p = Min(p, dp[G[x][i]][0] - dp[G[x][i]][2]);
dp[x][2] += dp[G[x][i]][2];
}
}
if(! flag)
dp[x][2] += p;
dp[x][0] ++; //如果自己有通讯塔，要加上自己的那一个
}
int main() {
n = read<int>();
for(reg int i = 1;i <= n - 1;i ++) {
int a = read<int>(), b = read<int>();
G[a].push_back(b); //用邻接表储存这棵树
G[b].push_back(a);
}
dfs(1); //dfs求解DP
write(Min(dp[1][2], dp[1][0]), '\n');
return 0;
}
```