CEOI2019

CEOI2019

D2T2 Magic Tree

请先思考后再展开

这题一开始乱想了想都不太行,然后立刻第一直觉就是dsu on tree,确实猜对了
设dp(x,time)然后先考虑序列,再考虑树,发现转移如下:
每次对每棵孩子的子树的整个dp序列做前缀mx,然后把各个孩子一一对应加起来,此时是递增的
然后如果x上有果实(time,val),那么dp(x,time)+=val,就是可能凸出来

为了让复杂度和子树大小相关,考虑只存储与前面不同的地方,并且仔细观察转移发现我们应当存储的是前缀mx后的结果
方向一:
直接存储具体的值,那么需要写一个动态开点权值线段树,然后到时候启发式合并就是后缀加
然后考虑x上果实的时候需要找到下一个比dp(x,time)+val更大的地方,中间删除,这个利用单调的特性是可以求的
这种写法应该是可行的,但码量较大,考虑怎么减小
方向二:
考虑差分,这个我确实没想到,主要是观察到我们需要的是后缀加,同时注意到差分后我们只需要处理val,而且中间要被删除
考虑每个数只会被删除一个,所以是可以暴力删除的,可以用map或者set来写,非常好写

上述两个方向的复杂度都是log方

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
const int N=1e5+10;
int fa[N],now[N];
map<int,ll> mp[N];typedef map<int,ll>::iterator IT;
int merg(int x,int y)
{
if(mp[x].size()>mp[y].size()) swap(x,y);
for(IT it=mp[x].begin();it!=mp[x].end();it++) mp[y][it->FR]+=(it->SE);
return y;
}
pr a[N];
void main()
{
int n=qread(),m=qread();qread();
for(int i=1;i<=n;i++) now[i]=i;
for(int i=2;i<=n;i++) fa[i]=qread();
for(int i=1;i<=m;i++){int x=qread(),t=qread(),val=qread();a[x]=MP(t,val);}
for(int i=n;i>=2;i--)
{
int t=now[i],ti=a[i].FR;ll val=a[i].SE,bkup=val;
mp[t][ti]+=val;IT gg=mp[t].find(ti);gg++;
while(gg!=mp[t].end())
{
IT tmp=gg;if(val<gg->SE){mp[t][gg->FR]-=val;break;}
val-=gg->SE;gg++;mp[t].erase(tmp);
}
now[fa[i]]=merg(now[fa[i]],t);
}
ll ans=0;for(IT it=mp[now[1]].begin();it!=mp[now[1]].end();it++) ans+=(it->SE);
write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2558.html
转载请注明出处,谢谢!