P3523 [POI2011]DYN-Dynamite

读错题题

读错题的题面:

给一棵树,您要选择m个地方放点,满足两两之间最小值最大

相当于二分答案后,每个点之间都要相差x....

然后这个显然可以N^2,但是O(n)?

贪心的想,我们坑定要从深度大的开始选才能最多

好像我们可以放一个点就把一些点缩起来,然后这些点之后一定不能再被选,而其他点一定可选,但是这样我们虽然保证了每次缩的是一个连通块,却不能在合法的时间复杂度里解决....

比如一个大块,然后边上有很多小点,每次我们判断能不能再缩都是O(n)的....QAQ

不过跑不太满

给一棵树,树上有一些关键节点,要求你选m个点,使得关键节点到这些点中距离的最小值的最大值最小,求这个值

也是考虑二分+贪心,那么我们对于二分出的值,我们要满足key点到放置点的距离不能大于了

所以可以从底层开始贪心,fif_i表示点i子树中最远的key点距离,gig_i表示点i子树最近的choice点距离

那么如果f_i+g_i<=mid,就可以凑齐,fif_i变为-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;
}