题解：P6847 [CEOI 2019] Magic Tree

· · 题解

:::info[题目大意]{open}

给定一棵以 1 为根的树，共 n 个节点。某些节点上长有果实，第 j 个果实在第 d_j 天成熟，收获可获得 w_j 点果汁。

每天可以割任意多条边。割边后，不含根的连通块会掉落到地面，其中恰好在当天成熟的果实被收获，不成熟或已过期的果实被丢弃。

求能获得的最大果汁总量。

:::

设 f(i,j) 表示：以 i 为根的子树中，在第 j 天或之前砍若干树枝，能获得的最多果汁。

  1. 不收获 i 的果实

    f_{i,j} =\sum_{son} f_{son,j}

  2. 收获 i 的果实

    前提：d_i \le j

    f_{i,j}=f_{i,f_i}+w_i

两个情况不能同时成立，取 \max。

显然，对每个节点 u 维护一棵以时间为下标的线段树，就可以用线段树合并优化 DP。

每个果实的处理触发一次 change，创建 O(\log k) 个线段树节点。

线段树合并时，若遇到同值区间可直接 O(1) 完成，均摊每次合并 O(\log k)。

总节点数 O(m \log k)，总时间复杂度是 O((n + m) \log k) 的。

实际运行中，同值压缩使得大量节点被回收（w_push_up 中 max == min 时删儿子），常数较小。

动态开点线段树节点总数大概是 O(m \log k)。n, k \le 10^5 时，开 5 \times 10^6 个节点足够。

注意到 w_i \le 10^9,n \le 10^5，总收益可能超过 int，必须用 long long。

:::info[code]{open}

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,m,k,x,w_cnt,w_head[100005],w[100005],d[100005],w_size[100005];
int w_index,w_root[100005];
struct node{
    int w_next,w_to;
}w_edge[100005];
struct Node{
    int w_lson,w_rson;
    long long w_min,w_max,w_tag;
}w_tree[5000005];
void w_add(int u,int v)
{
    w_edge[++w_cnt]={w_head[u],v};
    w_head[u]=w_cnt;
}
void w_push_up(int p)
{
    w_tree[p].w_max=max(w_tree[w_tree[p].w_lson].w_max,w_tree[w_tree[p].w_rson].w_max);
    w_tree[p].w_min=min(w_tree[w_tree[p].w_lson].w_min,w_tree[w_tree[p].w_rson].w_min);
    if(w_tree[p].w_max==w_tree[p].w_min)
        w_tree[p].w_lson=w_tree[p].w_rson=0;
}
void w_push_down(int p)
{
    if(!w_tree[p].w_tag)
        return;
    w_tree[w_tree[p].w_lson].w_max+=w_tree[p].w_tag;
    w_tree[w_tree[p].w_lson].w_min+=w_tree[p].w_tag;
    w_tree[w_tree[p].w_lson].w_tag+=w_tree[p].w_tag;
    w_tree[w_tree[p].w_rson].w_max+=w_tree[p].w_tag;
    w_tree[w_tree[p].w_rson].w_min+=w_tree[p].w_tag;
    w_tree[w_tree[p].w_rson].w_tag+=w_tree[p].w_tag;
    w_tree[p].w_tag=0;
}
void w_merge(int &p,int l,int r,int x)
{
    if(!p||!x)
    {
        p+=x;
        return;
    }
    if(w_tree[p].w_max==w_tree[p].w_min)
    {
        w_tree[x].w_max+=w_tree[p].w_max;
        w_tree[x].w_min+=w_tree[p].w_max;
        w_tree[x].w_tag+=w_tree[p].w_max;
        p=x;
        return;
    }
    if(w_tree[x].w_max==w_tree[x].w_min)
    {
        w_tree[p].w_max+=w_tree[x].w_max;
        w_tree[p].w_min+=w_tree[x].w_max;
        w_tree[p].w_tag+=w_tree[x].w_max;
        return;
    }
    int w_mid=l+r>>1;
    w_push_down(p);
    w_push_down(x);
    w_merge(w_tree[p].w_lson,l,w_mid,w_tree[x].w_lson);
    w_merge(w_tree[p].w_rson,w_mid+1,r,w_tree[x].w_rson);
    w_push_up(p);
}
void w_change(int &p,int l,int r,int x,int y,long long z)
{
    if(!p)
        p=++w_index;
    if(w_tree[p].w_min>=z)
        return;
    if(x<=l&&r<=y&&w_tree[p].w_max<=z)
    {
        w_tree[p].w_max=z;
        w_tree[p].w_min=z;
        w_tree[p].w_tag=0;
        w_tree[p].w_lson=w_tree[p].w_rson=0;
        return;
    }
    int w_mid=l+r>>1;
    w_push_down(p);
    if(w_tree[p].w_max==w_tree[p].w_min)
    {
        w_tree[p].w_lson=++w_index;
        w_tree[p].w_rson=++w_index;
        w_tree[w_tree[p].w_lson].w_max=w_tree[p].w_max;
        w_tree[w_tree[p].w_lson].w_min=w_tree[p].w_max;
        w_tree[w_tree[p].w_rson].w_max=w_tree[p].w_max;
        w_tree[w_tree[p].w_rson].w_min=w_tree[p].w_max;
    }
    if(x<=w_mid)
        w_change(w_tree[p].w_lson,l,w_mid,x,y,z);
    if(y>w_mid)
        w_change(w_tree[p].w_rson,w_mid+1,r,x,y,z);
    w_push_up(p);
}
long long w_query(int p,int l,int r,int x)
{
    if(!p)
        return 0;
    if(w_tree[p].w_max==w_tree[p].w_min)
        return w_tree[p].w_max;
    int w_mid=l+r>>1;
    w_push_down(p);
    if(x<=w_mid)
        return w_query(w_tree[p].w_lson,l,w_mid,x);
    else
        return w_query(w_tree[p].w_rson,w_mid+1,r,x);
}
void w_dfs(int u)
{
    w_root[u]=++w_index;
    for(int i=w_head[u];i;i=w_edge[i].w_next)
    {
        w_dfs(w_edge[i].w_to);
        w_merge(w_root[u],1,k,w_root[w_edge[i].w_to]);
    }
    if(d[u])
    {
        long long x=w_query(w_root[u],1,k,d[u]);
        w_change(w_root[u],1,k,d[u],k,x+w[u]);
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        w_add(x,i);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        scanf("%d %d",&d[x],&w[x]);
    }
    w_dfs(1);
    printf("%lld",w_tree[w_root[1]].w_max);
    return 0;
}

:::