洛谷 P1552 【APIO2012】派遣题解

xiaoh 2020-5-6

题意

有一棵含有 $n$ 个节点的有根树( $1\leq n\leq 10^5$ )以及一个阈值 $m$ ( $1\leq m\leq 10^9$ ),每个节点都有两个点权 $c_i,l_i$ ( $1\leq c_i\leq m,1\leq l_i\leq 10^9$ ).你需要选定一些节点,要求选定的节点的 $\sum c_i\leq m$ ,同时你需要选择一个”管理者“节点 $w$ ,管理者不一定需要在选定的节点中,但是一定要满足它 $w$ 任何被选中的节点都是祖先-后代关系.一个满足条件的方案的权值为 $l_w\times$ 节点数量.求权值的最大值.

题解

假设管理者的位置时固定的,那么此时我们可以采用贪心的策略,贪心的选取子树中点权最小的点直至超出阈值即可.

那么如果管理者的位置会变化又该怎样处理呢？同样是维护贪心策略,这让我们想到了十二省联考中的“春节十二响”这道题,我们可以类似的用堆去进行维护.对于每一个节点,我们用一个堆存下满足以其为管理者时贪心选择的所有节点,每次像树形 $DP$ 一样递归子树后合并,合并时若堆中放入当前元素仍然不超过阈值就直接将其插入,否则若当前元素小于堆中最大的一个元素就直接将其替换掉即可.然后再套一个 $dsu$ 的板子缩一下复杂度就行了,时间复杂度 $O(n\log^2 n)$ .(时限有一点紧,如果用 $stl$ 的话建议吸口氧气,不然有一个点容易超时.)

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
int n,m;
int fa[MAXN];
int son[MAXN],nxt[MAXN],hd[MAXN];
int tot=1;
inline void add_edge(register int u,register int v)//加儿子
{
    son[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
int a[MAXN];
int b[MAXN];
priority_queue<int> q[MAXN];
int rt[MAXN];
int sum[MAXN];
long long ans=0;
inline int merge(register int x,register int y)//合并
{
    if(q[rt[x]].size()<q[rt[y]].size()) swap(rt[x],rt[y]),swap(sum[x],sum[y]);//启发式合并
    while(!q[rt[y]].empty())
    {
        int k=q[rt[y]].top();q[rt[y]].pop();
        if(sum[x]+k<=m) q[rt[x]].push(k),sum[x]+=k;
        else if(k<q[rt[x]].top()) sum[x]-=q[rt[x]].top(),q[rt[x]].pop(),q[rt[x]].push(k),sum[x]+=k;
    }
    return rt[x];
}
void dfs(register int p)//递归求解
{
    for(register int i=hd[p];i;i=nxt[i])
    {
        dfs(son[i]);
        rt[p]=merge(p,son[i]);
    }
    ans=max(ans,(long long)q[rt[p]].size()*b[p]);
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;++i)
    {
        read(fa[i]),read(a[i]),read(b[i]);
        if(fa[i]) add_edge(fa[i],i);
        if(a[i]<=m) q[i].push(a[i]),sum[i]+=a[i];
        rt[i]=i;
    }
    dfs(1);
    write(ans),putchar('\n');
	return 0;
}