Luogu P3408 恋爱

题目链接：Click here

Solution:

设f[x]表示要使x向它的父亲写信需要花的最少的钱，per[x]为要使x向它的父亲写信最少要多少人

则\(f[x]=\sum_{i=1}^{per[x]}f[son[x]]\)，此时的f数组是从小到大排过序的

那我们只需要把每个点的儿子放到multiset去维护就好了，最后输出f[0]

总时间复杂度\(O(n\,log\,n)\)

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+1;
const int inf=2147483647;
int n,m,t,cnt,head[N];
int ans,a[N],per[N],cost[N],num[N];
struct Edge{int nxt,to;}edge[N];
struct cmp{bool operator()(const int& a,const int& b)const{return cost[a]<cost[b];}};
multiset<int,cmp> q[N];
multiset<int,cmp>::iterator it;
void ins(int x,int y){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;head[x]=cnt;
}
void dfs(int x){
    int flag=0;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        dfs(y);q[x].insert(y);
        flag=1;
    }
    if(!flag){cost[x]=a[x];return ;}
    if(x){
        int u=per[x];it=q[x].begin();
        for(int i=1;i<=u;i++){
            if(it==q[x].end()){
                cost[x]=inf;
                return ;
            }cost[x]+=cost[*it],++it;
        }
    }else{int w=(m*num[x]+t-1)/t;
        it=q[x].begin();
        for(int i=1;i<=w;i++)
            ans+=cost[*it],++it;
    }
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    n=read(),t=read(),m=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        ins(x,i);a[i]=y;num[x]++;
    }
    for(int i=1;i<=n;i++) per[i]=(num[i]*a[i]+t-1)/t;
    dfs(0);printf("%lld\n",ans);
    return 0;
}

Luogu P3408 恋爱

原文：https://www.cnblogs.com/NLDQY/p/11140874.html