链接：https://www.luogu.com.cn/problem/P4322
题目描述：给定一棵树，每个节点有两个权值\(a,b\)，每个节点要选了它的父亲节点才能选，求选\(k\)个人后\(a\)的和除以\(b\)的和的最小值。
题解：话说这道题我只会\(O(n^3logn)\)，尽管复杂度不对但还是水过了洛谷的数据。
\(a\)的和除以\(b\)的和的最小值让我们很容易想到\(0/1\)分数规划，然后这道题就变成了一道树型\(dp\)。
我们可以令\(dp_{i,j}\)表示在\(i\)的子树中选\(j\)个节点的最小代价。
则\(dp_{i,j}=\min(dp_{v,k}+dp_{i,j-k})\)，这样是\(O(n^3logn)\)的。
然后我们\(dp\)时将每一个点将\(j\)的上界设为\(sz_{i}\)，转移时\(j\)的下界设为\(j-sz_{i}+sz_{v}\),据说这样就是\(O(n^2logn)\)的了。
#include<iostream>
#include<cstdio>
using namespace std;
struct node
{
int v,nxt;
};
node edge[2501];
int len,head[2501],fa[2501],sz[2501],k,n,R[2501],S[2501],P[2501];
double delta[2501],dp[2501][2502];
bool used[2501];
inline void add(register int x,register int y)
{
edge[++len].v=y;
edge[len].nxt=head[x];
head[x]=len;
return;
}
inline void dfs(register int x)
{
dp[x][1]=delta[x];
sz[x]=used[x]=1;
for (register int i=head[x];i>0;i=edge[i].nxt)
if (!used[edge[i].v])
{
dfs(edge[i].v);
fa[edge[i].v]=x;
sz[x]+=sz[edge[i].v];
}
for (register int i=head[x];i>0;i=edge[i].nxt)
if (fa[edge[i].v]==x)
for (int j=sz[x];j>=2;--j)
for (int k=max(1,j-sz[x]+sz[edge[i].v]);k<=min(sz[edge[i].v],j);++k)
dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[edge[i].v][k]);
return;
}
inline bool check(register double L)
{
for (register int i=1;i<=n;++i)
delta[i]=P[i]-L*S[i];
for (register int i=0;i<=n;++i)
{
used[i]=0;
for (int j=0;j<=n+1;++j)
dp[i][j]=-1e9;
}
dfs(0);
return dp[0][k]>=0;
}
inline int read()
{
register char c=0;
register int sum=0;
while (c<'0'||c>'9')
c=getchar();
while (c>='0'&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
int main()
{
k=read();
n=read();
k++;
for (int i=1;i<=n;++i)
{
S[i]=read();
P[i]=read();
R[i]=read();
add(R[i],i);
}
double first=0,last=1e9,mid;
while (first+1e-5<=last)
{
mid=(first+last)/2;
if (check(mid))
first=mid;
else
last=mid;
}
printf("%0.3lf\n",first);
return 0;
}