BZOJ 4726: [POI2017]Sabota

Description

某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x,那么这个人也会变成叛徒,并且他的所有下属都会变成叛徒。你要求出一个最小的x,使得最坏情况下,叛徒的个数不会超过k。

Input

第一行包含两个正整数n,k(1<=k<=n<=500000)。
接下来n-1行,第i行包含一个正整数p[i+1],表示i+1的父亲是p[i+1](1<=p[i+1]<=i)。

Output

输出一行一个实数x,误差在10^-6以内都被认为是正确的。

Sample Input

9 3
1
1
2
2
2
3
7
3

Sample Output

0.6666666667

HINT

答案中的x实际上是一个无限趋近于2/3但是小于2/3的数
因为当x取2/3时,最坏情况下3,7,8,9都是叛徒,超过了k=3。

Source

鸣谢Claris上传

Solution

对于每个点i我们定义f_i:表示这个点如果不黑化最小的k是多少,答案就是所有子树大小大于k的点的f_i的最大值。
怎么求出f_i?

不难想到,不黑化最小=黑化最大(因为是实数),因此这个点要想黑化最大的k是多少就是f_i。
考虑i的孩子节点j:如果j感染到了i,那么一定满足j首先被感染,然后j所占比例超过了x然后才会感染i。
j被感染:f_j
j所占比例:size[j]/(size[i]-1)
这两个如果同时满足,那么一定取最小值(x=0时一定满足,x=1时可能都不满足)。
因此递推式子就有了:
\[ f_i = \max \{ \min \{ f_j, size[j] / (size[i] – 1) \} \} | (i \rightarrow j ) \]
\[ ans = \max \{ f_i \} \]

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 500001;
inline void getint(int &r) {
	r = 0; bool b = false; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar());
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
}
double dp[maxn], ans;
int n, m, cnte, h[maxn], siz[maxn], fa[maxn];
struct EDGE { int to, next; } edge[maxn];
inline void ins(int x, int y) {
	edge[++cnte].to = y;
	edge[cnte].next = h[x];
	h[x] = cnte;
}
int dfs(int now) {
	siz[now] = 1;
	for (int i = h[now]; i; i = edge[i].next)
		if (fa[now] != edge[i].to)
			siz[now] += dfs(edge[i].to);
	dp[now] = siz[now] == 1 ? double(1) : double(0);
	for (int i = h[now]; i; i = edge[i].next)
		if (fa[now] != edge[i].to)
			dp[now] = max(dp[now], min(double(siz[edge[i].to]) / double(siz[now] - 1), dp[edge[i].to]));
	if (siz[now] > m)
		ans = max(ans, dp[now]);
	return siz[now];
}
int main() {
	getint(n); getint(m);
	for (int i = 2; i <= n; ++i) {
		getint(fa[i]);
		ins(fa[i], i);
	}
	dfs(1);
	printf("%.10lf", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据