BZOJ 4726 Sabotaż

发表于 | 更新于

Link

Solution

一眼二分答案+树形DP，写出来之后T了？ 好吧。 正解是一遍树形DP，需要总结一些性质，挺有意思 首先，一个点如果不被子节点策反，那它的父节点也一定不会被策反 然后，一个点如果被策反了，那只要在父节点的子树中占比小，父节点也不会被策反 然后就DP： 设f[pos]f[pos]表示节点pospos不被策反的最小比例 对应上面两种情况，有 f[pos]=max{min{f[u],size[u]size[pos]−1}},u∈son[pos]f[pos]=max\{min\{f[u],\dfrac {size[u]}{size[pos]-1}\}\},u\in son[pos] 边界情况f[pos]=1,son[pos]==∅f[pos]=1,son[pos]==\emptyset 思路对我来说比较新奇，挺有意思

Tips

计算的新思路：先不管某一条性质，求出所有的答案之后再对满足这条性质的点的答案进行处理

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//Code by Lucida
#include<bits/stdtr1c++.h>
//Universal Declarations
typedef long long int64;
template <class T> inline void get(T &);
template <class T> inline void put(T);
template <> inline void put<double>(double);
template <class T> inline bool chkmx(T &,const T &);
template <class T> inline bool chkmn(T &,const T &);
using std::swap;
using std::max;
using std::min;

//Main Program
const int MAXN=500000+11;
const double eps=1e-7;
inline int fcmp(const double &x) {
	return -eps<x && x<eps?0:(x<0?-1:1);
}
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void* operator new(size_t);
}*id[MAXN];
void *Edge::operator new(size_t) {
	static Edge *Me=(Edge*)malloc(MAXN*sizeof(Edge));
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
}
int sz[MAXN];
double f[MAXN];
//f[pos]表示pos不被策反的最小rate
//u被策反，sz[u]/(sz[pos]-1)比f[u]小就行
void DP(int pos) {
	sz[pos]=1;
	if(!id[pos])
		f[pos]=1;
	else {
		f[pos]=0;
		for(Edge *e=id[pos];e;e=e->pre) {
			int u=e->to;
			DP(u);
			sz[pos]+=sz[u];
		}
		for(Edge *e=id[pos];e;e=e->pre) {
			int u=e->to;
			chkmx(f[pos],min(f[u],1.0*sz[u]/(sz[pos]-1)));
		}
	}
}
int main() {
	int n,K;get(n),get(K);
	for(int i=2;i<=n;++i) {
		int fa;get(fa);
		Adde(fa,i);
	}
	DP(1);
	double Ans=0;
	for(int i=1;i<=n;++i)
		if(sz[i]>K) chkmx(Ans,f[i]);
	put(Ans),putchar('\n');
	return 0;
}

//Universal Definitions
template <class T> inline void get(T &x) {
	static bool f;static char ch;
	for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
	for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
	x=f?-x:x;
}
template <class T> inline void put(T x) {
	printf("%d",x);
}
template <> inline void put<double>(double x) {
	printf("%lf",x);
}
template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}