题解 P3408 【恋爱】

momo5440 · 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;//从根开始遍历 
}