[CEOI2019] 魔法树

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

一、题目

点此看题

二、解法

首先选子树为 \(dp\) 主体，但是考虑没有时间做不动，我们假设子树 \(u\) 是在时间 \(i\) 被断开的，也就是断开操作是由于 \(u\) 的祖先引起的。设 \(dp[u][i]\) 表示子树 \(u\) 在 \(i\) 时间内被断开最后能得到的最大果汁，转移讨论 \(u\) 这个点的果汁：

• 不获取 \(u\) 点的果汁：\(dp[u][i]=\sum dp[v][i]\)
• 断开父边，获取 \(u\) 点的果汁：\(dp[u][x]=w_u+\sum dp[v][d_u]\)，其中 \(x\geq d_u\)

显然可以用线段树合并来优化，第一种转移就直接线段树合并，第二种转移不能维护区间最值标记，因为这样就不能合并。因为 \(dp[u][i]\) 关于 \(i\) 单调所以第二种转移可以考虑成区间赋值。

具体实现中区间赋值不打标记，而是线段树上的点维护 \(\min,\max\)，如果 \(\min=\max\) 的时候就说明这个区间是一个值，线段树合并的时候如果遇到区间同值的情况就打加法标记，修改的时候如果区间同值就新开儿子节点，上传的时候如果发现区间同值可以把儿子节点删掉（方便理解，避免出锅）

那么时间复杂度 \(O(n\log n)\)，警告：一定不要尝试去维护区间赋值标记，很难。

还有一种小清新的优化方法，因为 \(dp\) 值单调所以可以考虑差分，那么第一种转移就能直接启发式合并，第二种转移是增加 \(w_u\) 的差分值，直接插入 \(\tt set\) 中，这其实是取 \(\max\) 操作，所以要从后面删除一些差分标记，时间复杂度 \(O(n\log^2n)\)，但是比线段树合并要少 \(100\) 多行。

三、总结

\(\tt think\ twice,code\ once\)，后期发现一个思路是否错误的能力真的很重要。

当 \(dp\) 值单调且需要合并的时候可以考虑维护差分值。线段树合并是加法标记是最支持的，其他好像都不怎么好。

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
const int N = 100*M;
#define ll long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,tot,f[M],d[M],w[M],rt[M];
int cnt,ls[N],rs[N];ll mi[N],ad[N],mx[N];
struct edge
{
	int v,next;
}e[M];
int same(int x)
{
	return !ls[x] && !rs[x];
}
void add(int x,ll y)
{
	if(!x) return ;
	mi[x]+=y;mx[x]+=y;ad[x]+=y;
}
void up(int x)
{
	mx[x]=max(mx[ls[x]],mx[rs[x]]);
	mi[x]=min(mi[ls[x]],mi[rs[x]]);
	if(mx[x]==mi[x]) ls[x]=rs[x]=0;//delete
}
void down(int x)
{
	if(ad[x])
	{
		add(ls[x],ad[x]);
		add(rs[x],ad[x]);
		ad[x]=0;
	}
}
int merge(int x,int y)
{
	if(!x || !y) return x+y;
	if(same(y))
	{
		add(x,mx[y]);
		return x;
	}
	if(same(x))
	{
		add(y,mx[x]);
		return y;
	}
	down(x);down(y);
	ls[x]=merge(ls[x],ls[y]);
	rs[x]=merge(rs[x],rs[y]);
	up(x);
	return x;
}
ll ask(int x,int l,int r,int p)
{
	if(same(x)) return mx[x];
	int mid=(l+r)>>1;down(x);
	if(mid>=p) return ask(ls[x],l,mid,p);
	return ask(rs[x],mid+1,r,p);
}
void upd(int &x,int l,int r,int L,int R,ll v)
{
	if(l>R || L>r || mi[x]>=v) return ;
	if(mx[x]<=v && L<=l && r<=R)
	{
		mx[x]=mi[x]=v;
		ls[x]=rs[x]=ad[x]=0;
		return ;
	}
	int mid=(l+r)>>1;down(x);
	if(same(x))
	{
		ls[x]=++cnt;rs[x]=++cnt;
		mx[ls[x]]=mi[ls[x]]=mx[rs[x]]=mi[rs[x]]=mx[x];
	}
	upd(ls[x],l,mid,L,R,v);
	upd(rs[x],mid+1,r,L,R,v);
	up(x);
}
void dfs(int u)
{
	rt[u]=++cnt;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		dfs(v);
		rt[u]=merge(rt[u],rt[v]);
	}
	if(d[u]) upd(rt[u],1,k,d[u],k,w[u]+ask(rt[u],1,k,d[u]));
}
signed main()
{
	n=read();m=read();k=read();
	for(int u=2;u<=n;u++)
	{
		int v=read();
		e[++tot]=edge{u,f[v]},f[v]=tot;
	}
	for(int i=1;i<=m;i++)
	{
		int v=read();
		d[v]=read();w[v]=read();
	}
	dfs(1);
	printf("%lld\n",mx[rt[1]]);
}

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