什么是点覆盖问题？
就是在树上选几个点，覆盖（一个点可以覆盖其相连的边或与其距离不超过 \(d\) 的点，根据题意具体分析）一些点或边，求最小代价。
例题
战略游戏
题意
一棵无根树，一个点可以覆盖与其相连的边，求将整棵树的边覆盖，最少需要放置几个点。
思路
可以发现，根是哪个点，对答案没有影响，那我们就假定1为根，来简化问题。
这样每条边肯定就是连着父亲和儿子，要么被父亲覆盖，要么被儿子覆盖，或者被父亲和儿子一起覆盖。
每个节点都有放和不放两种状态。
设\(dp[i][0/1]\)表示该节点不放和放可以将以i为根的子树的边覆盖的最小代价。
- \(dp[i][0]+=dp[son[i]][1]\)
该点不放，它和它儿子的边就得由儿子来覆盖，儿子必须放。 - \(dp[i][1]+=min(dp[son[i]][0],dp[son[i]][1])\)
该点放，它和它儿子的边已经被该点覆盖，儿子放不放都行，取最小。 - \(ans=min(dp[i][0],dp[i][1])\)
答案来自1号节点放或不放（可以将整棵子树覆盖的最小代价），两者取最小。
时间复杂度：\(O(n)\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,dp[1505][2];
vector<int> g[1505];
void dfs(int x,int fa){
dp[x][1]=1;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
dfs(v,x);
dp[x][0]+=dp[v][1];
dp[x][1]+=min(dp[v][0],dp[v][1]);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
int u=read()+1,x=read();
while(x){
x--;
int v=read()+1;
g[u].push_back(v);
g[v].push_back(u);
}
}
dfs(1,0);
cout<<min(dp[1][0],dp[1][1]);
return 0;
}
VOCV - Con-Junctions
题意
一棵无根树，一个点可以覆盖与其相连的边，求将整棵树的边覆盖，最少需要放置几个点。并求出最小代价的方案数。
思路
对于第一问，和上一题一样，不再赘述。
来看第二问，求最小代价的方案数。
维护一个 \(g[i][0/1]\)， 表示该节点不放和放可以将以 \(i\) 为根的子树的边覆盖的最小代价的方案数。
在 \(dp\) 值转移时进行维护。\(g\) 的初始值都为1。
- \(dp[i][0]+=dp[son[i]][1]\)，该 \(dp\) 值只能由所有儿子都放转移过来。\(g[i][0]*=g[son[i]][1]\)。
- \(dp[i][1]+=min(dp[son[i]][0],dp[son[i]][1])\)，该 \(dp\) 值有两种转移途径，分三种情况。
- \(dp[son[i]][0]<dp[son[i]][1]\)，\(dp\) 值由 \(dp[son[i]][0]\) 转移过来。
\(g[i][1]*=g[son[i]][0]\) - \(dp[son[i]][0]>dp[son[i]][1]\)，\(dp\) 值由 \(dp[son[i]][1]\) 转移过来。
\(g[i][1]*=g[son[i]][1]\) - \(dp[son[i]][0]==dp[son[i]][1]\)，\(dp\) 值要么由 \(dp[son[i]][0]\) 转移过来，要么由 \(dp[son[i]][1]\) 转移过来，都可以。
\(g[i][1]*=(g[son[i]][0]+g[son[i]][1])\)
- 最后输出第一问：\(min(dp[1][0],dp[1][1])\)。
- 输出第二问：1. \(dp[1][0]<dp[1][1]\)
输出\(g[1][0]\)。
- \(dp[1][0]==dp[1][1]\)
输出 \((g[1][0]+g[1][1])%mod\) 一定要取模啊。 - \(dp[1][0]>dp[1][1]\)
输出\(g[1][1]\)。
时间复杂度：\(O(Tn)\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
const long long mod=10007;
int t,n,dp[100015][2];
long long g[100015][2];
vector<int> gg[100015];
void dfs(int x,int fa){
dp[x][0]=0,dp[x][1]=g[x][0]=g[x][1]=1;
for(int i=0;i<gg[x].size();i++){
int v=gg[x][i];
if(v==fa) continue;
dfs(v,x);
dp[x][0]+=dp[v][1];
dp[x][1]+=min(dp[v][0],dp[v][1]);
g[x][0]*=g[v][1];
if(dp[v][0]<dp[v][1]) g[x][1]*=g[v][0];
else if(dp[v][0]==dp[v][1]) g[x][1]*=(g[v][0]+g[v][1]);
else g[x][1]*=g[v][1];
g[x][0]%=mod,g[x][1]%=mod;
}
}
int main(){
t=read();
while(t){
t--;
n=read();
for(int i=1;i<=n;i++) gg[i].clear();
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
for(int i=1;i<n;i++){
int u=read(),v=read();
gg[u].push_back(v);
gg[v].push_back(u);
}
dfs(1,0);
if(dp[1][0]<dp[1][1]) cout<<dp[1][0]<<" "<<g[1][0]<<'\n';
else if(dp[1][0]==dp[1][1]) cout<<dp[1][0]<<" "<<(g[1][0]+g[1][1])%mod<<'\n';
else cout<<dp[1][1]<<" "<<g[1][1]<<'\n';
}
return 0;
}
将军令
题意
一棵树，1个点可以控制距离自己不超过 \(k\) 的节点，求将所有节点都控制住，最少需要多少节点。
思路
这道题用的是不太正经正规的 DP。（贪心 DP）。
考虑贪心，我们每次覆盖尽量多的节点，怎么覆盖呢。我们每次从深度最深的节点开始，选它的 \(k\) 级父亲覆盖。这样去贪心是正确的。它满足贪心的性质。1.问题具有子结构。2.这样决策无后效性。3.在此前提下（无后效性），没有比这样选更优的选法。（来自YWY_wys大佬的解释）
设 \(f[x][0]\)表示 \(x\) 到以该点为根的子树中最近的已放驿站节点的距离。
设\(f[x][1]\)表示 \(x\) 到以该点为根的子树中最远的未被控制节点的距离。
然后就不会讲了胡完了。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,k,t,f[100005][2],ans;
vector<int> g[100005];
void dfs(int x,int fa){
f[x][0]=0x3f3f3f3f;
f[x][1]=0;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
dfs(v,x);
if(f[v][1]!=-1) f[x][1]=max(f[x][1],f[v][1]+1);
f[x][0]=min(f[x][0],f[v][0]+1);
}
if(f[x][0]+f[x][1]<=k) f[x][1]=-1;
if(f[x][1]==k){
f[x][1]=-1;
f[x][0]=0;
ans++;
}
}
int main(){
n=read(),k=read(),t=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
if(f[1][1]==0) ans++;
cout<<ans;
return 0;
}