题解 P6847 【[CEOI2019] Magic Tree】

· · 题解

首先有一个显然的暴力dp

设 f_{u,t} 表示 t 时刻前断掉 u 和 u 的父亲这条边的最大收益

显然有 f_{u,t}=val(u,t)+\sum\limits_{v\in son(u)} f_{v,t}，val(u,t) 表示 t 时刻之前断掉 u 和 u 父亲这条边节点 u 的收益

有 val(u,t)=w_u\times [d_u\le t]

不难发现 f_u 是单调不降的，并且连续的一段值是相等的，而且拐点不会很多

于是，我们可以用一个 map 存储这些拐点，以及对应的 f 值

对于一个节点 u，和它的儿子 v，我们只要把 v 的 map 中所有值都加到 u 的 map 中即可

接下来考虑 u 自己的贡献，我们需要对所有 \ge d_u 的 f 都加上 w_u，于是就是要进行一个后缀加操作，可以把 map 中维护的东西换成 f 的差分数组（当然如果你直接用线段树维护的话直接区间加就行了）

每次暴力合并 map 显然会超时，于是用启发式合并

时间复杂度 \mathcal O(n\log n\log k)

code:

#include<bits/stdc++.h>
#define MAXN 100010
#define int long long
#define iter map<int,int>::iterator 
using namespace std;
int n,m,K;
int rt[MAXN],fa[MAXN],d[MAXN],w[MAXN];
map<int,int>f[MAXN];
void merge(int &a,int b){
    if(f[a].size()<f[b].size())swap(a,b);
    for(iter it=f[b].begin();it!=f[b].end();it++)
        f[a][it->first]+=it->second;
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&K);
    for(int i=2;i<=n;i++)scanf("%lld",&fa[i]);
    for(int i=1;i<=m;i++){
        int p;scanf("%lld",&p);
        scanf("%lld%lld",&d[p],&w[p]);
    }
    for(int i=1;i<=n;i++)rt[i]=i;
    for(int i=n;i;i--){
        f[rt[i]][d[i]]+=w[i];iter it;
        for(it=f[rt[i]].find(d[i]),it++;it!=f[rt[i]].end();){
            if(it->second>w[i]){it->second-=w[i];break;}
            w[i]-=it->second;iter tmp=it;it++;f[rt[i]].erase(tmp);
        }
        merge(rt[fa[i]],rt[i]);
    }int ans=0;
    for(iter it=f[rt[1]].begin();it!=f[rt[1]].end();it++)
        ans+=it->second;
    printf("%lld",ans);
    return 0;
}