【题解】P3408 恋爱

· · 题解

与其说是 DP，还不如说是树上递推+贪心。

类似的题还有 CSP-S2 2019 D1T2 括号树（树上递推），这一类题我们可以“递归地”思考。

首先只考虑一个结点和其所有子结点之间的关系： 设当前结点 u 的权值为 dp_u （由于笔者习惯，这里按照动态规划命名递推数组），若当前结点的子结点个数为 child_u ，根据题意，当已选子结点数量 selected_u 满足 {\frac{selected_u}{child_u} \ge \frac{a_i}{T}} 时，该结点可以对其父结点 w 的已选子结点个数 selected_w 做出 1 的贡献；若当前结点是根结点，代表此时有合法解。

接下来考虑计数：对于一个结点 u ，其权值 dp_u 为：若其为叶结点，则有 dp_u=a_u ；否则，设结点 u 的子结点集合为 childs_u ,已选择的子结点集合为 selects_u ，有 dp_u=\sum_{v\in{childs_u}}^{v\in{selects_u}}{dp_v} 。

该题的目的为最小化 dp_{root} ，那么对应地，容易得到两个贪心性质：

一：选择的子结点数应尽量小。

二：每次都尽量选择还未选过的权值最小的子结点。

以上性质可以递推到每个非叶结点上。

那么，我们可以很容易地总结出这道题每个结点上的贪心方法：逐个按照权值从小到大选点，一边选一边计算权值，一旦数量符合规定立刻停止选点。

而对于权值的计算，如果写题比较多的话应该也已经看出来了：先 dfs 到叶结点，之后返回向上递推计算每个结点的权值。

而维护每个结点最小值的方法可以是排序，也可以在每个结点进行 dfs 时开一个小根堆（优先队列），对于每个结点需要排序或进出（至少每个结点进一次，但可能不会每个结点都出一次）优先队列的个数等于其子结点数（若为叶结点则不需要该操作所以为 0 ），易得树上所有点的该操作次数为树的结点数。数据范围显然不能使用计数排序，则使用快速排序或堆的时间复杂度总计为 O({n\log n}) 。

AC代码：（注意：以上和分数有关的变量需要浮点数，最好都开 long double）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=5e5+11;
struct edge
{
    LL to,val,next;
}G[N];
LL head[N],cnt,n,t,c,a[N],dp[N],child[N];
bool vis[N];
long double kai;
struct Node
{
    LL ai;
}node[N];
inline void add_edge(LL u,LL v,LL val)
{
    G[cnt].to=v,G[cnt].val=val,G[cnt].next=head[u];head[u]=cnt++;
}
inline void dfs(LL u)
{
    vis[u]=1;
    if(child[u]==0) {dp[u]=node[u].ai;return;}
    priority_queue<LL,vector<LL>,greater<LL> > q;
    for(auto i=head[u];i!=-1;i=G[i].next)
    {
        LL v=G[i].to;
        if(!vis[v]) dfs(v);q.push(dp[v]);
    }
    long double fuckccf=node[u].ai/(t*1.0);//cout<<"FUCKCCF:"<<fuckccf<<endl;
    LL count=0;
    while((count/(child[u]*1.0))<fuckccf) {dp[u]+=q.top();q.pop();count++;}
}
inline LL read()
{
    LL a=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {a=a*10+(ch-'0');ch=getchar();}
    return a*f;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read(),t=read(),c=read();
    node[0].ai=c;
    for(auto i=1;i<=n;i++) {LL u=read();node[i].ai=read();add_edge(u,i,1);child[u]++;}
    dfs(0);
    cout<<dp[0];
    return 0;
}