题解,求关注

二、分析
这道题其实一眼看过去就是一个树形背包DP，但是这道题唯一特别的就是其中涉及到了分数。当我们求一个分数的最值的时候，我们通常使用的是二分。

1、分数规划
当题目中让我们求：∑ a i ∑ b i \frac{\sum a_i}{\sum b_i}
∑b
i
​

∑a
i
​

​
的最大值的时候，我们应该怎么做呢？

不妨设：
∑ a i ∑ b i = x \frac{\sum a_i}{\sum b_i}=x
∑b
i
​

∑a
i
​

​
=x

那么就有：
∑ a i = x m a x ∗ ∑ b i \sum a_i = x_{max} * \sum b_i
∑a
i
​
=x
max
​
∗∑b
i
​

即：

∑ a i − x m a x ∑ b i = 0 \sum a_i - x_{max}\sum b_i=0
∑a
i
​
−x
max
​
∑b
i
​
=0

我们可以将这几个求和融合一下：

∑ ( a i − x ∗ b i ) = 0 \sum(a_i-x*b_i)=0
∑(a
i
​
−x∗b
i
​
)=0

因此，我们可以让括号内的式子是C i C_iC
i
​

我们会发现一个特点∑ C i \sum C_i∑C
i
​
是关于x xx的单调函数，因此我们可以使用二分，而二分中的c h e c k checkcheck函数其实就是利用树形DP求出上面求和式的最大值，然后进行判断。

我们这里用到的二分是浮点数二分。

整个过程的时间复杂度是O ( n 2 l o g n ) O(n^2logn)O(n
2
logn)的。（树形背包DP看似是O ( n 3 ) O(n^3)O(n
3
)的，但实际上当我们对其上下界进行优化后，可以到达O ( n 2 ) O(n^2)O(n
2
)）。

2、树形DP
状态表示
f [ u ] [ j ] f[u][j]f[u][j]表示在以u uu为根的树（包括u uu）中选j jj个节点，∑ c i \sum c_i∑c
i
​
的最大值。

状态转移
f [ u ] [ j ] = m a x ( f [ u ] [ j ] , f [ u ] [ j − q ] + f [ s o n ] [ q ] ) f[u][j]=max\bigg(f[u][j],f[u][j-q]+f[son][q]\bigg)
f[u][j]=max(f[u][j],f[u][j−q]+f[son][q])

初末状态
f [ u ] [ 1 ] f[u][1]f[u][1]表示选一个，所以就是f [ u ] [ 1 ] = c [ u ] f[u][1]=c[u]f[u][1]=c[u]
f [ u ] [ 0 ] f[u][0]f[u][0]表示选0个，所以就是f [ u ] [ 0 ] = 0 f[u][0]=0f[u][0]=0

由于题目中选0 00节点不算进我们方案，但是我们在计算的时候，还是要算入我们的答案的，所以我们代码中选择的实际上是k + 1 k+1k+1个点。最终的状态即：f [ 0 ] [ k + 1 ] f[0][k+1]f[0][k+1]

三、代码

#include<bits/stdc++.h>
#define endl '\n'
#define INF  0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2500 + 10;
double f[N][N];
double p[N], s[N], c[N];
int siz[N];
vector<int>edge[N];
int n, k;

//f[u][j] => 在以u为根的树中，选择j个点，c的和的最大值。

void cal_siz(int u)
{
	siz[u] = 1;
	for(int i = 0; i < edge[u].size(); i ++)
	{
		cal_siz(edge[u][i]);
		siz[u] += siz[edge[u][i]];
	}
}

void dp(int u)
{
	f[u][0] = 0.0;
	f[u][1] = c[u];
	for(int i = 0; i < edge[u].size(); i ++ )
	{
		int son = edge[u][i];
		dp(son);
		for(int j = min(siz[u], k + 1); j >= 0; j -- )
			for(int q = 0; q <= min(siz[son], j - 1); q ++ )
			{
				if(f[u][j - q] == -INF || f[son][q] == -INF)
					continue;	
				f[u][j] = max(f[u][j], f[son][q] + f[u][j - q]);
			}
	}
}

bool check(double mid)
{
	for(int i = 0; i <= n; i ++ )
		for(int j = 0; j <= k + 1; j ++ )
			f[i][j] = -INF;
		
	for(int i = 1; i <= n; i ++ )
		c[i] = p[i] - mid * s[i];
	
	dp(0);

	return f[0][k + 1] >= 0.0;
}

double find()
{
	double l = 0.0, r = 5000;
	while(r - l > 1e-9)
	{
		double mid = (l + r) / 2;
		if(check(mid))
			l = mid;
		else
			r = mid;
		// cout << l << " " << r << endl;
	}
	return l;
}

void solve()
{
	cin >> k >> n;
	for(int i = 1; i <= n; i ++ )
	{
		int fa;
		cin >> s[i] >> p[i] >> fa;
		edge[fa].push_back(i);
	}
	cal_siz(0);

	printf("%.3lf", find());
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
}