自动搬运

查看原文

来自洛谷，原作者为

	momo5440 qwq

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

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

以下是正文

理论上来说这道题根本没有用到一点动态规划的思想，每个节点都取最优最后也是最优，所以这算是一道树上贪心？基本思路呢就是写一个dfs，从根（0）开始遍历对于非叶子节点求出它所有根的值（递归调用dfs）并压入一个优先队列（小根堆），取最上面的大于等于T分之Ai个然后返回它们和的值，对于叶子节点只要返回它的Ai就行了。 详情请见代码，我觉得是挺简短的。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;//只要空间足够就无脑开long long  
ll a[500005];//题目中每个人的 Ai 
vector<ll> bian[500005];//记录每个人的孩子 
ll n,t,c;//跟题目中一样 
ll dfs(ll x){
	if (bian[x].size()==0) return a[x];//是叶子节点，直接返回 Ai
	priority_queue< ll,vector<ll>, greater<ll> > q;//小根堆 
	for (ll i=0;i<bian[x].size();i++) q.push(dfs(bian[x][i]));//递归调用自己，求出自己孩子的值 
	ll ans=0;
	for (ll i=0;i<1.0*a[x]*bian[x].size()/t;i++){//记得写1.0这样才精确不然会自动取整 
		ans+=q.top();//取前T分之Ai个 
		q.pop();
	}
	return ans;//返回这个节点的值 
}
int main(){
	cin>>n>>t>>c;
	ll tp;
	for (ll i=1;i<=n;i++){
		cin>>tp>>a[i];
		bian[tp].push_back(i);
	}//读入数据并建树 
	a[0]=c;//小B本身的Ai就是c 
	cout<<dfs(0)<<endl;//从根开始遍历 
}