P3523 [POI2011]DYN-Dynamite
读错题题
读错题的题面:
给一棵树,您要选择m个地方放点,满足两两之间最小值最大
相当于二分答案后,每个点之间都要相差x....
然后这个显然可以N^2,但是O(n)?
贪心的想,我们坑定要从深度大的开始选才能最多
好像我们可以放一个点就把一些点缩起来,然后这些点之后一定不能再被选,而其他点一定可选,但是这样我们虽然保证了每次缩的是一个连通块,却不能在合法的时间复杂度里解决....
比如一个大块,然后边上有很多小点,每次我们判断能不能再缩都是O(n)的....QAQ
不过跑不太满
给一棵树,树上有一些关键节点,要求你选m个点,使得关键节点到这些点中距离的最小值的最大值最小,求这个值
也是考虑二分+贪心,那么我们对于二分出的值,我们要满足key点到放置点的距离不能大于了
所以可以从底层开始贪心,表示点i子树中最远的key点距离,表示点i子树最近的choice点距离
那么如果f_i+g_i<=mid,就可以凑齐,变为-inf
否则如果f_i==mid,就要把i设置为新点啦
你说莫名的TLE?我尼玛咋知道啊?
code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 1e7 + 7;
const int MAXN = 6e5 + 7;
int is[MAXN / 2], f[MAXN / 2], g[MAXN / 2], Cnt, n, m, Mid;
int home[MAXN], nxt[MAXN], to[MAXN], ccnt;
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
inline void dfs(int u, int F) {
f[u] = -inf;
g[u] = inf;
if(is[u])f[u] = 0;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
dfs(v, u);
f[u] = max(f[v] + 1, f[u]); //update f
g[u] = min(g[u], g[v] + 1); //update g
}
if(f[u] + g[u] <= Mid) {
f[u] = -inf;
}
if(f[u] == Mid) { //furthst
++Cnt;
g[u] = 0;
f[u] = -inf;
}
// printf("%d %d %d\n",u,f[u],g[u]);
return ;
}
inline int chk() {
Cnt = 0;
dfs(1, 0);
if(f[1] >= 0)Cnt++;
if(Cnt <= m)return 1;
else return 0;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)scanf("%d", &is[i]);
for(int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
ct(x, y);
ct(y, x);
}
int L = 0, R = n, ans;
while(L <= R) {
Mid = (L + R) >> 1;
if(chk()) {
ans = Mid;
R = Mid - 1;
} else L = Mid + 1;
}
printf("%d\n", ans);
return 0;
}