HeinzHuang

Eudaimonia

0%

Magic Tree（CF-1193B CEOI 2019 Day 2）

Posted on Edited on In

Magic Tree（CF-1193B CEOI 2019 Day 2）

题目描述：

给一个\(n\)节点的树，其中有\(m\)个点有果实，分别在编号为\(pi\)的点上，在第\(di\)天成熟，在成熟的那天收割有\(wi\)的贡献。给出\(K,di<=K\). 通过断开树上的边来收割果实，每断开一个边，取不包含根的子树，获得上面所有成熟果实的贡献值，剩下的全部丢弃。每天都可以断任意条边。 问总共能收获到的最大贡献。

思路：

这题有一个比较重要的结论，就是在第\(j\)天割一条边\([x,f]\)时，如果\(x\)点为根的子树也有断掉的边时，那么这些边割掉的时间都必须小于等于\(j\)，其实也算不上啥结论，想想就知道了。

子任务1

有上面的结论就比较简单了，状压枚举哪些果实要获得贡献，然后\(dfs\)一遍判断时间上是否合法。 即如果有一个果实\(x\)是\(v\)的祖先，且都被选，但\(D[v]>D[x]\)就不合法了。代码比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool dfs(int x){
	if(mark[x]==ti)mxd[x]=D[x];
	EOR(G,i,x){
		int v=G.to[i];
		if(!dfs(v))return false;
		if(mark[x]==ti&&D[x]<mxd[v])return false;
		chkmax(mxd[x],mxd[v]);
	}
	return true;
}
void solve(){
	ll ans=0;
	loop(i,1<<m){
		ti++;//时间戳
		ll sum=0;
		loop(j,m)if(i>>j&1)
			mark[A[j+1].p]=ti,sum+=A[j+1].w;
		FOR(j,1,n)mxd[j]=0;
		if(dfs(1))chkmax(ans,sum);
	}
	printf("%lld\n",ans);
}
子任务2

没啥好说的，全加。

子任务3

是一条链，且每个点贡献为\(1\),相当于数个数。用上面的结论可知，其实就是从下到上\(LIS\)一下。

子任务4，5

个人把两个合并起来了。。感觉分\(K<=2\)没啥意义。。
考虑\(f[n][k]\)数组。\(f[x][j]\)表示在以\(x\)为根，前\(j\)天能收割到的最大值。 那么，我们有转移方程：

\[ f[x][j]=max((\sum f[v][D[x]])+W[x],\sum f[v][j]) (j>=D[x]) \]

\[ f[x][j]=\sum f[v][j](j<D[x]) \]

应该不难理解，代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int x){
	EOR(G,i,x){
		int v=G.to[i];
		dfs(v);
		FOR(j,0,K)f[x][j]+=f[v][j];
	}
	f[x][D[x]]+=W[x];
	FOR(i,1,K)chkmax(f[x][i],f[x][i-1]);
}
void solve(){
	dfs(1);
	ll ans=0;
	FOR(j,0,K)chkmax(ans,f[1][j]);
	printf("%lld\n",ans);
}

子任务6,7,8（正解）

这里可以在分点打（个人觉得没啥必要）。。 考虑原来的转移方程，其实每个\(f[x]\)最初都是一个后缀，然后每次还会将所有儿子的状态合并上来，显然想到线段树合并，每棵树维护一个点的装态，最后向上合并即可。

但是，还可以用启发式合并写，代码短且比较简练。 对每个节点开个\(map\)（\(set< pair >\)也行，随便）.表示每个点的\(dp\)状态，由于从子节点转移上来都是用加法所以直接循环合并加上来即可

1
2
3
4
if(mp[x].size()<mp[v].size())
    swap(mp[x],mp[v]);
for(it=mp[v].begin();it!=mp[v].end();it++)
    mp[x][(*it).X]+=(*it).Y;

然后就是关键了，就是如何更新最大前缀。 还记得\(\sum f[v][D[x]]+W[x]\)吗？这个值有可能更新掉\(j>=D[x]\)的所有边，所以不仅仅是直接插入一个点那么简单了。我们把每个在它之后的点都扫一遍，如果当前点的w值大于插入值\(val\)，说明当前前缀更优，但由于\(val\)会影响所有在当前位置之后的前缀，所以要在当前位置上减掉。否则，就在\(val\)上减掉该值，并将枚举点删除。表示当前前缀被更新为新前缀

1
2
3
4
5
6
7
8
9
10
11
mp[x][D[x]]+=W[x];//加入一个新点（即一个新前缀）
it=mp[x].upper_bound(D[x]);
ll val=W[x];//表示新前缀最后一个点的值
while(it!=mp[x].end()){
	ll w=it->Y;//当前前缀的最后一个点值
	if(w>=val){
		it->Y-=val;//使得当前前缀保持不变
		break;
	}
	val-=w;mp[x].erase(it++);//新前缀更优，删去原前缀的最后一个点值
}

这个过程一定要好好理解，这种用点维护前缀的思想很重要。 #### AC代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#define FOR(i,l,r) for(int i=(l),i##R=(r);i<=i##R;i++)
#define DOR(i,r,l) for(int i=(r),i##L=(l);i>=i##L;i--)
#define loop(i,n) for(int i=0,i##R=(n);i<i##R;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define lowbit(x) (x&(-x))
#define pb push_back
#define X first
#define Y second
typedef long long ll;
using namespace std;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int N=1e5+5;
int n,m,K;
int fa[N];
struct Graph{
	int tot,to[N<<1],nxt[N<<1],head[N];
	void add(int x,int y){tot++;to[tot]=y;nxt[tot]=head[x];head[x]=tot;}
	void clear(){mms(head,-1);tot=0;}
	#define EOR(G,i,x) for(int i=G.head[x];i!=-1;i=G.nxt[i])
}G;
struct Fruit{
	int p,d,w;
}A[N];
int D[N],W[N];
map<int,ll>mp[N];
map<int,ll>::iterator it;
void dfs(int x){
	EOR(G,i,x){
		int v=G.to[i];
		dfs(v);
		if(mp[x].size()<mp[v].size())swap(mp[x],mp[v]);
		for(it=mp[v].begin();it!=mp[v].end();it++)mp[x][(*it).X]+=(*it).Y;
	}
	mp[x][D[x]]+=W[x];
	it=mp[x].upper_bound(D[x]);
	ll val=W[x];
	while(it!=mp[x].end()){
		ll w=it->Y;
		if(w>=val){
			it->Y-=val;
			break;
		}
		val-=w;mp[x].erase(it++);
	}
}
int main(){
	G.clear();
	scanf("%d%d%d",&n,&m,&K);
	FOR(i,2,n){
		scanf("%d",&fa[i]);
		G.add(fa[i],i);
	}
	FOR(i,1,m){
		scanf("%d%d%d",&A[i].p,&A[i].d,&A[i].w);
		D[A[i].p]=A[i].d;
		W[A[i].p]=A[i].w;
	}
	dfs(1);
	ll ans=0;
	for(it=mp[1].begin();it!=mp[1].end();it++)
		ans+=it->Y;
	printf("%lld\n",ans);
	return 0;
}