LibreOJ 3166 「CEOI2019」魔法树

设 fu,i 表示第 i 天收获 u 点时 u 子树内的答案。

考虑合并 u 和儿子 v 的答案。
有 f′u,i=max{imaxj=0{fu,i+fv,j}.imaxj=0{fu,j+fv,i}}

发现是一个 max 卷积的形式，可以考虑使用线段树合并维护。
复杂度 O(nlogn)。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m,k;
int d[N + 5],w[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
    struct node
    {
        long long val,tag;
        int ls,rs;
    } seg[(N << 6) + 5];
    inline void push(int p)
    {
        if(seg[p].tag)
        {
            if(seg[p].ls)
                seg[seg[p].ls].val += seg[p].tag,
                seg[seg[p].ls].tag += seg[p].tag;
            if(seg[p].rs)
                seg[seg[p].rs].val += seg[p].tag,
                seg[seg[p].rs].tag += seg[p].tag;
            seg[p].tag = 0;
        }
    }
    void insert(int x,long long k,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (seg[p = ++tot] = seg[0],1),seg[p].val = max(seg[p].val,k);
        if(tl == tr)
            return ;
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
    }
    long long query(int r,int p,int tl,int tr)
    {
        if(!p || r >= tr)
            return seg[p].val;
        push(p);
        int mid = tl + tr >> 1;
        long long ret = -0x3f3f3f3f3f3f3f3f;
        ret = max(ret,query(r,seg[p].ls,tl,mid));
        r > mid && (ret = max(ret,query(r,seg[p].rs,mid + 1,tr)));
        return ret;
    }
    long long val(int x,int p,int tl,int tr)
    {
        if(tl == tr)
            return seg[p].val;
        push(p);
        int mid = tl + tr >> 1;
        return x <= mid ? val(x,seg[p].ls,tl,mid) : val(x,seg[p].rs,mid + 1,tr);
    }
    int merge(int p,int q,long long ptag,long long qtag,int tl,int tr)
    {
        if(!p && !q)
            return 0;
        if(!p)
        {
            seg[q].val += qtag,seg[q].tag += qtag;
            return q;
        }
        if(!q)
        {
            seg[p].val += ptag,seg[p].tag += ptag;
            return p;
        }
        if(tl == tr)
        {
            ptag = max(ptag,seg[q].val),qtag = max(qtag,seg[p].val);
            seg[p].val = max(seg[p].val + ptag,seg[q].val + qtag);
            return p;
        }
        push(p),push(q);
        int mid = tl + tr >> 1;
        long long plval = seg[seg[p].ls].val;
        long long qlval = seg[seg[q].ls].val;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,ptag,qtag,tl,mid);
        seg[p].rs = merge(seg[p].rs,seg[q].rs,max(ptag,qlval),max(qtag,plval),mid + 1,tr);
        seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
        return p;
    }
}
int fa[N + 5];
int rt[N + 5];
void dfs(int p)
{
    for(register int i = first[p];i;i = pre[i])
        dfs(to[i]),
        rt[p] = SEG::merge(rt[p],rt[to[i]],0,0,1,N);
    d[p] && (SEG::insert(d[p],w[p] + max(SEG::query(d[p],rt[p],1,N),0LL),rt[p],1,N),1);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(register int i = 2;i <= n;++i)
        scanf("%d",fa + i),add(fa[i],i);
    int x,y,z;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d",&x,&y,&z),d[x] = y,w[x] = z;
    dfs(1);
    printf("%lld\n",SEG::seg[rt[1]].val);
}