自动搬运

查看原文

来自洛谷，原作者为

	青葱 rush

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

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

以下是正文

前置知识：

树形DP

其实无所谓，和普通DP差不多

大致思路：

看到价值和重量，不管三七二十一，直接考虑背包

然后再看一下数据范围，value和weight的范围极大，不能用传统的以价值作为下标的背包

但是n很小，仅到100，所以考虑以件数作为下标

转移方程：

设f[u][i]表示:
在以u为根的子树中，选择i个节点，所能得到的最大平均值

当然，记录最大平均值的同时，也要记录权值和与重量和，方便转移

那么自然有：

对于u的每棵子树v:
f[u][j]=f[v][k]+f[u][j-k];
其中，j-k>=1，因为要保证联通，所以u这个节点是必选的

具体做法：

首先，我开了一个结构体，用于存储状态

struct node{
	int v,w;double ave;//转移状态的权值和，重量和，平均值
	node(){}
	node(int a,int b,double p):v(a),w(b),ave(p){}
}f[E][E];

然后dfs

void dfs(int u,int fa){
	f[u][1]=node(val[u],wei[u],(double)val[u]/wei[u]);//初始化
	for(int i=head[u];i;i=nex[i])
		if(to[i]!=fa){//不能走回父亲
			dfs(to[i],u);//先遍历子树
			for(int j=n;j>1;j--){//注意，这里一定要逆序，否则重复选择该棵子树的点
				for(int k=1;k<=j;k++){
					node p=f[to[i]][j-k];
					node q=f[u][k];
					double ave=(double)(p.v+q.v)/(p.w+q.w);
					if(ave>=f[u][j].ave){
						f[u][j]=node(p.v+q.v,p.w+q.w,ave);
					}
				}
			}
		}
}

好了，完了

最终的代码

复杂度O(n^3)

#include<bits/stdc++.h>
#define E 209
#define inf 1e8
using namespace std;
inline int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return x;
}
int n,kk,m,wei[E],val[E];
int head[E],nex[E],to[E],cnt;
inline void add(int u,int v){
	nex[++cnt]=head[u];
	head[u]=cnt;to[cnt]=v;
}
struct node{
	int v,w;double ave;
	node(){}
	node(int a,int b,double p):v(a),w(b),ave(p){}
}f[E][E];
void dfs(int u,int fa){
	f[u][1]=node(val[u],wei[u],(double)val[u]/wei[u]);
	for(int i=head[u];i;i=nex[i])
		if(to[i]!=fa){
			dfs(to[i],u);
			for(int j=n;j>1;j--){
				for(int k=1;k<=j;k++){
					node p=f[to[i]][j-k];
					node q=f[u][k];
					double ave=(double)(p.v+q.v)/(p.w+q.w);
					if(ave>=f[u][j].ave){
						f[u][j]=node(p.v+q.v,p.w+q.w,ave);
					}
				}
			}
		}
}
int main(){
	n=read(),kk=read();
	for(int i=1;i<=n;i++) val[i]=read();
	for(int i=1;i<=n;i++) wei[i]=read();
	for(int i=1,v,u;i<n;i++){
		u=read(),v=read();
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=node(-inf,inf,-inf);
	dfs(1,0);double ans=0.0;
	for(int i=1;i<=n;i++)
		for(int j=kk;j<=n;j++){
//			cout<<i<<" "<<j<<" "<<f[i][j].v<<" "<<f[i][j].w<<endl;
			ans=max(ans,f[i][j].ave);
		}
	printf("%.2f",ans);
	return 0;
}