【题解】魔法树 Magic Tree [CEOI2019] [CF1193B] [Loj3166]

传送门：魔法树 ( ext{Magic Tree}) ( ext{[CEOI2019]}) ( ext{[CF1193B]}) ( ext{[Loj3166]})

【题目描述】

给出一颗 (n) 个节点的树（根为 (1)），每个节点 (i) 会在第 (d_i) 天时放出量为 (w_i) 的妹汁。在每一天 (j) 您可以砍掉树上的任意一些边，若当天与节点 (1) 不再联通的点的 (d_i) 恰好等于 (j)，您可以获得这些妹汁。

求总共最多能收获多少妹汁。

【分析】

先考虑暴力 (dp)，设 (f(x,j)) 表示在时间 (j) 时以 (x) 为根的子树可获得的最大妹汁量，则有：

(f(x,j)=max{f(x,j-1),g(x,j)})，其中 (g(x,j)=w(x)*[j=d(x)]+sum_{toin son(x)}f(to,j))

复杂度 (O(nk))，可以过 ( ext{Subtask 1,4,5})，有 (34pts) 。

用个小 (trick) 优化转移。

注意到 (f) 实际上是 (g) 的前缀最大值，给每个点开个 (map) 记录 (j) 和 (f(x,j)-f(x,k)) ((k<j,f(x,k) eq f(x,j)))（相邻两个不同前缀最大值的差），那坨子树累加直接启发式合并。

每次给 (g(x,d(x))) 加上 (w(x)) 后都会使从 (d(x)) 开始的连续一段发生改变，先 ( ext{upperbound}) 找到 (d(x)) 位置后面的第一个指针，然后依次往后移动并删去被更新掉的位置，无法继续更新时就停止（利用差分的良好性质）。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#define LL long long
#define Re register int
#define IT map<int,LL>::iterator
using namespace std;
const int N=1e5+3;
int n,m,x,y,o,T,K,t[N],v[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Sakura1{//暴力
    LL ans,dp[N][23];
    inline void dfs(Re x){
        for(Re i=head[x],to;i;i=a[i].next){
            dfs(to=a[i].to);
            for(Re j=0;j<=K;++j)dp[x][j]+=dp[to][j];
        }
        dp[x][t[x]]+=v[x];
        for(Re j=t[x]+1;j<=K;++j)dp[x][j]=max(dp[x][j],dp[x][j-1]);
    }
    inline void sakura(){dfs(1),printf("%lld
",dp[1][K]);}
}T1;
struct Sakura2{//正解
    int id[N];LL ans;map<int,LL>s[N];
    inline void dfs(Re x){
        id[x]=x;
        for(Re i=head[x],to;i;i=a[i].next){
            dfs(to=a[i].to);
            if(s[id[x]].size()<s[id[to]].size())swap(id[x],id[to]);
            for(IT it=s[id[to]].begin();it!=s[id[to]].end();++it)
                s[id[x]][it->first]+=it->second;
        }
        s[id[x]][t[x]]+=v[x];LL dlt=v[x];IT it=s[id[x]].upper_bound(t[x]),tmp;
        while(it!=s[id[x]].end())
            if(dlt>=it->second)dlt-=it->second,tmp=it++,s[id[x]].erase(tmp);//f(x,d(x))更优，删掉这个点
            else{it->second-=dlt;break;}//这个点更优，结束枚举
    }
    inline void sakura(){
        dfs(1);
        for(IT it=s[id[1]].begin();it!=s[id[1]].end();++it)ans+=it->second;//差分回收
        printf("%lld
",ans);
    }
}T2;
int main(){
//    freopen("magic.in","r",stdin);
//    freopen("magic.out","w",stdout);
    in(n),in(T),in(K),m=n-1;
    for(Re i=2;i<=n;++i)in(x),add(x,i);
    while(T--)in(x),in(t[x]),in(v[x]);
//    if(K<=20)T1.sakura();else
    T2.sakura();
}