题目链接
题目大意:
就是一棵5e35e35e3的树,可以选择一些点,放上基站,如果uuu上的基站价值为ddd,那么距离uuu小于等于ddd的点都会被覆盖,问使得整棵树被覆盖需要的最小价值。
解题思路:
-
一开始我是这么想树形dp的 dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值dp[i][j]表示覆盖完i子树并且i节点放置权值为j的覆盖站的所需要的最小价值
-
但是这里有两个问题就是如果你是有根树:你每个点的放置一个权值为www的信号站,不仅会覆盖到儿子节点,也会覆盖到祖先节点,这样dpdpdp不容易实现,因为你不知道它向上影响了多远?
-
那么我们为什么不把那个影响距离带到dpdpdp方程里面去呢?
-
dp[u][j]表示覆盖完u这个子树并且能够覆盖到所有向上距离它≤j所有点的最小代价是多少?dp[u][j]表示覆盖完u这个子树并且能够覆盖到所有向上距离它\leq j所有点的最小代价是多少?dp[u][j]表示覆盖完u这个子树并且能够覆盖到所有向上距离它≤j所有点的最小代价是多少?
-
那么我们知道向上影响距离是jjj无非两种情况就是
(1):在u这个位置直接放置权值为jjj的基站
(2):子树传递影响上去 -
对于子树直接放置权值为jjj的基站我们知道它的影响是两个方向的有儿子也有祖先:那么根据贪心原理dp[u][j]=j+g[u][j+1],g[u][j+1]:覆盖距离u距离≥j的所有dp[u][j]=j+g[u][j+1],g[u][j+1]:覆盖距离u距离\ge j的所有dp[u][j]=j+g[u][j+1],g[u][j+1]:覆盖距离u距离≥j的所有儿子节点所需要的最小代价(注意这里是只有儿子)
-
如果是子树传递上去的呢?
dp[u][j]=min{dp[sonu][j+1]+(g[u][j+1]−g[sonu][j])}dp[u][j]=min\{dp[son_u][j+1]+(g[u][j+1]-g[son_u][j])\}dp[u][j]=min{dp[sonu][j+1]+(g[u][j+1]−g[sonu][j])}
为啥要减掉g[sonu][j]g[son_u][j]g[sonu][j]因为贡献重复计算了 -
那么ggg数组怎么算呢?很好算的g[u][i]+=g[sonu][i−1]g[u][i]+=g[son_u][i-1]g[u][i]+=g[sonu][i−1]
-
注意点1:就是dp[u][0]=0+g[u][1]dp[u][0]=0+g[u][1]dp[u][0]=0+g[u][1]这是不合法的因为实际上并没有包含到uuu节点,那么dp[u][0]dp[u][0]dp[u][0]只能算第二种情况就是子树传递贡献上去!!
-
注意点2:就是实际上dp[u][i+1]dp[u][i+1]dp[u][i+1]是对dp[u][i]dp[u][i]dp[u][i]有贡献影响的,因为覆盖范围≥i+1\ge i+1≥i+1肯定也≥i\ge i≥i,ggg数组同理也是g[u][i−1]g[u][i-1]g[u][i−1]对g[u][i]g[u][i]g[u][i]是用贡献的因为距离≤i−1\leq i-1≤i−1肯定也≤i\leq i≤i
-
注意点3:g[u][0]=dp[u][0]g[u][0]=dp[u][0]g[u][0]=dp[u][0]
AC code
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 5010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);
}
int n, lim = 5000;
vector<int> G[maxn];
int dp[maxn][maxn]; // dp[u][j] 表示覆盖完u这个子树并且覆盖了上面所有距离<=j的祖先节点最小费用
int g[maxn][maxn]; // g[u][i] 表示覆盖了距离u >= i的所有节点所需要的最小费用
void dfs(int u, int fa) {int min_son = -1;for(auto it : G[u]) {if(it == fa) continue;dfs(it,u);for(int i = 1; i <= lim; ++ i) g[u][i] += g[it][i-1];if(min_son == -1 || dp[it][1] < dp[min_son][1])min_son = it;}if(G[u].size() == 1 && u != 1) dp[u][0] = 1; // 叶子节点为1else dp[u][0] = dp[min_son][1] + g[u][1] - g[min_son][0];dp[u][lim] = INF;// 把边界设置成无穷大for(int i = lim - 1; i >= 1; -- i) {dp[u][i] = g[u][i+1] + i;for(auto it : G[u]) if(it != fa) {dp[u][i] = min(dp[it][i+1]-g[it][i]+g[u][i+1],dp[u][i]);}} // 处理一下同层之间的贡献for(int i = lim-1; i >= 0; -- i) dp[u][i] = min(dp[u][i],dp[u][i+1]); g[u][0] = dp[u][0]; // g的边界for(int i = 1; i <= lim; ++ i) g[u][i] = min(g[u][i],g[u][i-1]);
}int main() {IOS;cin >> n;for(int i = 1; i < n; ++ i) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);} dfs(1,0);cout << g[1][0];return 0;
}