[CEOI2019]Magic Tree

2021/7/29 23:10:07

编程Tag： return Tree int LS MX Magic RS CEOI2019 tre

本文主要是介绍[CEOI2019]Magic Tree，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

壹、题目描述 ¶

传送门 to Luogu.

贰、题解 ¶

◆ 前言

真的降智了，那么明显的性质都没有被发现......

◆ 暴力的想法

一眼树 \(\rm DP\) ？考虑设计状态 \(f(u,j)\) 表示在 \(j\) 时刻割掉 \(u\) 与其父亲的边的最大收益。那么我们就有转移式子：

\[f(u, j)=w_u[d_u=j]+\sum_{v\in son_u} \max_{k=0}^j f(v, k) \]

单次转移是 \(\mathcal O(k)\) 的，那么总复杂度就是 \(\mathcal O(nk^2)\) 了。

但是，我们发现该转移有一个东西 —— 前缀取最大值，并且我们显然可以通过更改状态定义简化转移，因而，我们更改状态定义为 \(f(u, j)\) 表示在小于等于 \(j\) 时刻去掉 \(u\) 与其父亲的连边，能获得的最大收益，此时状转就变成了

\[f(u, j)=\max\left\{f(u, j-1), w_u[d_u=j]+\sum_{v\in son_u} f(v, j)\right\} \]

再做复杂度就是 \(\mathcal O(nk)\) 的了。

◆ Observation

对题目性质进行一些观察，首先，我们单考虑一条链，肯定是找 \(\rm LIS\)，这不必说。

如果在树上，假设我们在 \(t\) 时刻切掉 \(u\) 与其父亲的连边，那么，我们能在 \(u\) 子树中选择的，就是那些 \(d\le t\) 的点了，即，时间越晚，能够选择的点越多，又即，切边时间 \(t\) 与收益存在正比的关系，也即，\(f(u, j)\) 与 \(j\) 存在正比关系。

◆ 简化转移

显然，该算法瓶颈在于转移，我们试图简化转移，根据上面的 \(f(u, j)\) 与 \(j\) 成正比增长，对于一个固定点 \(u\)，我们存在推论：

\[\sum_{v\in son_u} f(v, j_1)\le \sum_{v\in son_u}f(v, j_2)\quad (j_1<j_2) \]

既然时间越大，儿子的函数值求和越大，那么我们是否可以继续将我们的转移去掉与前缀比最大？即将转移改写为：

\[f(u, j)=w_u[d_u=j]+\sum_{v\in son_u} f(v, j) \]

这显然不对，问题在于当 \(j=d_u\) 时，改时刻对应函数值不只是儿子求和，另多一项 \(w_u\)，不过，我们可以在 \(j=d_u\) 时刻做一个分界线：

  • 当 \(j<d_u\) 时，有 \(f(u, j)=\sum f(v,j)\)；
  • 当 \(j\ge d_u\) 时，有 \(f(u, j)=\max\left\{f(u, j-1), w_u[j=d_u]+\sum_{v\in son_u} f(v, j)\right\}\)；

并且，这个 \(\max\) 的真正含义似乎不必再单纯理解为是前缀最大了，由于儿子求和具有单调性，那么当 \(d_u+1<j_1<j_2\) 时，显然存在 \(j_1\) 时刻儿子求和大于 \(j_2\) 时刻儿子求和，而我们 \(\max\) 想要的作用，事实上是将 \(w_u+\sum f(v, d_u)\) 传递到后面，即，将 \(w_u+\sum f(v, d_u)\) 与 \(f(u, j)(j\in [d_u, k])\) 的每个元素取最大值。

那么我们现在再来看看转移：

  • 当 \(j<d_u\) 时，有 \(f(u, j)=\sum f(v,j)\)；
  • 当 \(j\ge d_u\) 时，有 \(f(u, j)=\max\left\{w_u+\sum f(v, d_u), w\sum_{v\in son_u} f(v, j)\right\}\)；

不难发现每一项都有 \(\sum f(v,j)\)，我们可以先将每一项都赋值为 \(\sum f(v,j)\)，然后再将 \([d_u, k]\) 中每一项与 \(w_u+\sum f(v, d_u)\) 取最大值。而这可以使用线段树合并在 \(\mathcal O(\log n)\) 的时间内解决。

所以，总复杂度 \(\mathcal O(n\log n)\). 需要实现线段树合并。

来自神 _LPF_ 的代码细节提示：

不考虑使用普通线段树的区间赋值标记（比较难合并），而是记录下区间 \(\min,\max\)，如果一个区间 \(\min=\max\)，则说明该区间所有元素都相同，

合并时直接被合并，更新时直接删掉左右儿子，修改时添加左右儿子，就相当于有了区间赋值的作用了。

就没有了。

叁、参考代码 ¶

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('\n')
    #define mmset(a, b) memset(a, b, sizeof a)
    // #define int long long
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='\n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

const int maxn=1e5;
const int logn=30;
const ll inf=1ll<<50;

vector<int>Delshack;
int rt[maxn+5], ncnt;
struct node{
    int ls, rs;
    ll mx, mn, tag;
}tre[maxn*logn+5];
inline int apply(){
    int ret;
    if(!Delshack.empty()){
        ret=Delshack.back();
        Delshack.pop_back();
    }
    else ret=++ncnt;
    return ret;
}
inline void collapse(int& u){
    if(!u) return;
    tre[u].ls=tre[u].rs=0;
    tre[u].mx=tre[u].mn=tre[u].tag=0;
    Delshack.push_back(u);
    u=0;
}
inline void add(int u, ll val){
    if(!u) return;
    tre[u].mx+=val, tre[u].mn+=val;
    tre[u].tag+=val;
}
inline void pushdown(int u){
    if(!tre[u].tag) return;
    add(tre[u].ls, tre[u].tag);
    add(tre[u].rs, tre[u].tag);
    tre[u].tag=0;
}
inline void pushup(int u){
    tre[u].mx=max(tre[tre[u].ls].mx, tre[tre[u].rs].mx);
    tre[u].mn=min(tre[tre[u].ls].mn, tre[tre[u].rs].mn);
    if(tre[u].mx==tre[u].mn)
        collapse(tre[u].ls), collapse(tre[u].rs);
}
inline bool same(int u){
    return tre[u].mx==tre[u].mn;
}
int merge(int u, int v){
    if(!u || !v) return u|v;
    if(same(u)) return add(v, tre[u].mx), v;
    if(same(v)) return add(u, tre[v].mx), u;
    pushdown(u), pushdown(v);
    tre[u].ls=merge(tre[u].ls, tre[v].ls);
    tre[u].rs=merge(tre[u].rs, tre[v].rs);
    return pushup(u), u;
}
ll query(int u, int l, int r, int pos){
    // printf("query:> u == %d, l == %d, r == %d, pos == %d\n", u, l, r, pos);
    if(same(u)) return tre[u].mx;
    pushdown(u);
    int mid=(l+r)>>1;
    if(pos<=mid) return query(tre[u].ls, l, mid, pos);
    else return query(tre[u].rs, mid+1, r, pos);
}
void modify(int u, int l, int r, int L, int R, ll x){
    if(tre[u].mn>=x) return;
    if(L<=l && r<=R && tre[u].mx<=x){
        tre[u].mx=tre[u].mn=x, tre[u].tag=0;
        collapse(tre[u].ls), collapse(tre[u].rs);
        return;
    }
    pushdown(u);
    if(same(u)){
        tre[u].ls=apply(), tre[u].rs=apply();
        tre[tre[u].ls].mn=tre[tre[u].rs].mn=tre[u].mn;
        tre[tre[u].ls].mx=tre[tre[u].rs].mx=tre[u].mx;
    }
    int mid=(l+r)>>1;
    if(L<=mid) modify(tre[u].ls, l, mid, L, R, x);
    if(mid<R) modify(tre[u].rs, mid+1, r, L, R, x);
    pushup(u);
}

void print(int u, int l, int r){
    printf("tre[%d]  [%d, %d]  :> ls == %d, rs == %d, mx == %lld, mn == %lld\n", u, l, r, tre[u].ls, tre[u].rs, tre[u].mx, tre[u].mn);
    if(same(u)) return;
    print(tre[u].ls, l, (l+r)>>1), print(tre[u].rs, ((l+r)>>1)+1, r);
}


vector<int>g[maxn+5];
int d[maxn+5], w[maxn+5];
int n, m, k;

inline void add_edge(int u, int v){
    g[u].push_back(v);
}

inline void input(){
    n=readin(1), m=readin(1), k=readin(1);
    int par;
    for(int i=2; i<=n; ++i){
        par=readin(1);
        add_edge(par, i);
    }
    for(int i=1; i<=m; ++i){
        par=readin(1);
        d[par]=readin(1), w[par]=readin(1);
    }
}

void dfs(int u){
    // printf("Now u == %d\n", u);
    rt[u]=apply();
    for(int v: g[u])
        dfs(v), rt[u]=merge(rt[u], rt[v]);
    if(d[u]){
        ll val=query(rt[u], 1, k, d[u]);
        // printf("val == %lld\n", val);
        modify(rt[u], 1, k, d[u], k, val+w[u]);
    }
    // printf("<---------------- the tre of node %d ---------------->\n", u);
    // print(rt[u], 1, k);
    // Endl; Endl;
}

signed main(){
    input();
    dfs(1);
    writc(tre[rt[1]].mx);
    return 0;
}

肆、关键之处 ¶

挖掘出 \(f(u, j)\) 具有单调性是最重要的。



这篇关于[CEOI2019]Magic Tree的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程