题解 P3408 【恋爱】

abandentsky · 2019-10-30 11:23:35 · 个人记录

题意：很简单啊就是选择叶子节点，使得最后的根节点也能签字。但就是AC不了啊操。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define MAXN 1000005
#define mod 100000000
#define INF 0x3f3f3f3f
using namespace std;

int n,t,c;
struct Edge
{
    int from,to;
    Edge(int from=0,int to=0):from(from),to(to){};
};
vector<Edge> edges;
vector<int> G[MAXN];
int val[MAXN],dp[MAXN],Q[MAXN];

bool comp(int a,int b)
{
    return a<b;
}

int dfs(int root)                                                                  //这个题目一定要看清题意，只有叶子节点是可以受贿的，其他节点是由儿子节点决定的
{
    if(G[root].size()==0)                                                    //让叶子节点签字的最小花费就是叶子节点的花费
    {
        return dp[root]=val[root];
    }
    int leaves=G[root].size();                                              //root的儿子节点个数
    for(int i=0;i<leaves;i++)
    {
        Edge &e=edges[G[root][i]];
        Q[i]=dfs(e.to);                                                             //这个子节点的最小签字花销等于子树签字的最小开销街上自己签字的花销
    }
    sort(Q,Q+leaves,comp);                                              //由小到大的排序
    int cnt;                                                                            //计算出让root节点签字的最小子节点个数
    if((leaves*val[root])%t==0)
        cnt=leaves*val[root]/t;
    else
        cnt=leaves*val[root]/t+1;
    if(root==0)                                                                      //并不是全树的每个节点都是一样的
    {
        if((leaves*c)%t==0)
            cnt=leaves*c/t;
        else
            cnt=leaves*c/t+1;
    }
    int sum=0;                                                                     //计算出和
    for(int i=0;i<cnt;i++)
        sum+=Q[i];
    return sum;                                                               //返回能让root节点签字的最小个数
}

int main()
{
    scanf("%d %d %d",&n,&t,&c);
    int B;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&B,&val[i]);
        edges.push_back({B,i});                    //父节点到这个节点
        int mm=edges.size();
        G[B].push_back(mm-1);
    }
    printf("%d\n",dfs(0));                            //0就是根节点，直接输出就好了
    return 0;
}