自动搬运

查看原文

来自洛谷，原作者为

	YLWang 别等到一千年以后 所有人都遗忘了我

搬运于2025-08-24 21:58:58，当前版本为作者最后更新于2019-10-08 19:10:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树上背包的复杂度是$O(n^2)$的。

首先可以看出这是一道分数规划的题，二分答案$mid$操作一波就变成了了以下这道题：

给定一棵根为$0$的树。每个点点权为$P_i-mid *S_i$，选定一个点就必须选其所有祖先节点。问能否取$k$个节点使得取出的点点权大于零。

不防设$dp[u][j]$表示当前根为$u$，取$j$个节点所带来的收益最大值。

则有两种情况：

• 1.$u$不取。则这棵树一个都不能取。$dp[u][0] = 0$

• 2.$u$取。枚举子树，设子树的根为$v$。枚举当前已合并的所有子树取的总个数$j$以及该子树内取的个数$k$。有$dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);$注意因为$u$取，所以必须强制跳过状态$dp[u][0]$，即$j$与$j-k$均不为$0$.

关于时间复杂度网上有一篇讲稿 十分不错，引用一段：

• ... 因为每次合并一棵子树时付出的代价是”已经合并的兄弟子树的大小之和”*”正在合并的这棵子树的大小”,实质上是树上每对节点在LCA处贡献时间复杂度 ...

所以是$n^2$的。

代码如下：

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define reaD() read()
#define pb push_back
#define mst(a,b) memset(a,b,sizeof(a))
#define foR(i, k, j) for(register int i = (k); i >= (j); i--)
#define For(i, k, j) for(register int i = (k); i <= (j); i++)
#define DEBUG printf("Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
using namespace std;
inline void ckmax(int &a, int b) {a = max(a, b);}
inline void ckmin(int &a, int b) {a = min(a, b);}
inline int read()
{
    int num=0,flag=1;char c=' ';
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag = -1;
    for(;c>='0'&&c<='9';num=(num<<1)+(num<<3)+c-48,c=getchar());
    return num*flag;
}
#define MAXN 2505
struct Edge {
	int v, nxt; 
}e[MAXN<<1];
int lst[MAXN], tot, n, m;
inline void addedge(int u, int v) {
	e[++tot] = (Edge) {v, lst[u]};
	lst[u] = tot;
}
double U[MAXN], V[MAXN];
double a[MAXN], dp[MAXN][MAXN];
double tmp[MAXN];
int siz[MAXN];
inline void dfs(int u, int fa) {
	dp[u][1] = a[u]; siz[u] = 1;
	for(int i = lst[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if(v != fa) {
			dfs(v, u);
			siz[u] += siz[v];
			for(int j = min(siz[u], m+1); j >= 1; j--)
				For(k, 0, min(siz[v], j-1))
					dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
		}
	}
}
inline bool check(double mid) {
	a[0] = 0;
	For(i, 1, n) a[i] = U[i]-mid*V[i];
	For(i, 0, n) 
		For(j, 1, m+1) dp[i][j] = -1e9;
	dfs(0, -1);
	return dp[0][m+1] >= 0;
}
signed main()
{
//	freopen("snakes.in", "r", stdin);
//	freopen("snakes.out", "w", stdout);
	cin >> m >> n;
	For(i, 1, n) {
		V[i] = read(), U[i] = read();
		addedge(read(), i);
	}
	double l = 0, r = 10000;
	while(l < r - 1e-4) {
		double mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	printf("%.3lf\n", l);
    return 0;
}