题目背景

刚立完Flag我就挂了WC和THUWC。。。

时间限制0.5s,空间限制128MB

因为Claris大佬帮助一周目由乃通过了Deus的题,所以一周目的由乃前往二周目世界找雪辉去了

由于二周目世界被破坏殆尽,所以由乃和雪辉天天都忙着重建世界(其实和MC差不多吧),Deus看到了题问她,总是被告知无可奉告

Deus没办法只能去三周目世界问三周目的由乃OI题。。。

三周目的世界中,因为没有未来日记,所以一切都很正常,由乃天天认真学习。。。

因为Deus天天问由乃OI题,所以由乃去学习了一下OI

由于由乃智商挺高,所以OI学的特别熟练

她在RBOI2016中以第一名的成绩进入省队,参加了NOI2016获得了金牌保送

Deus:这个题怎么做呀?

yuno:这个不是NOI2014的水题吗。。。

Deus:那如果出到树上,多组链询问,带修改呢?

yuno:诶。。。???

Deus:这题叫做睡觉困难综合征哟~

虽然由乃OI很好,但是她基本上不会DS,线段树都只会口胡,比如她NOI2016的分数就是100+100+100+0+100+100。。。NOIP2017的分数是100+0+100+100+0+100

所以她还是只能找你帮她做了。。。

题目描述

由乃这个问题越想越迷糊,已经达到了废寝忘食的地步。结果她发现……晚上睡不着了!只能把自己的一个神经元(我们可以抽象成一个树形结构)拿出来,交给Deus。

这个神经元是一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。

为了治疗失眠,Deus可以将一些神经递质放在点x上,初始的刺激值是

v0v_0

。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的刺激值尽可能大,所以最大值的v可以是多少呢?当然由于初始的神经递质的量有限,所以给定的初始值

v0v_0

必须是在[0,z]之间。Deus每次都会给你3个数,x,y,z。

不过,Deus为了提升治疗效果,可能会对一些神经节点进行微调。在这种情况下,也会给三个数x,y,z,意思是把x点的操作修改为y,数值改为z

输入输出格式

输入格式:

第一行三个数n,m,k。k的意义是每个点上的数,以及询问中的数值z都

<2k<2^k

。之后n行,每行两个数x,y表示该点的位运算编号以及数值

之后n – 1行,每行两个数x,y表示x和y之间有边相连

之后m行,每行四个数,Q,x,y,z表示这次操作为Q(1位询问,2为更改),x,y,z意义如题所述

输出格式:

对于每个操作1,输出到最后可以造成的最大刺激度v

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

输入样例#2: 复制

输出样例#2: 复制

说明

对于30%的数据,n,m <= 1

对于另外20%的数据,k <= 5

对于另外20%的数据,位运算只会出现一种

对于100%的数据,0 <= n , m <= 100000 , k <= 64

很早之前就看到过和起床困难综合症分不清

还是考虑按位贪心 具体参考起床起床困难综合症

需要回答询问的时候就把这条链切出来询问即可

那么怎么维护这个题解提供了一种简洁的方法  我把信息分开维护 维护lo.f0 表示从左起一开始全是0的一直做操作到我这个位置的信息 lo.f1表示左起一开始全是1的一直操作到我这里 ro同理

假如说我们有两段带合并的已经计算出答案的区间,分别对应f0,f1和g0,g1。我们设合并后的答案是h0,h1,那么有如下式子:

h0=(~f0&g0)+(f0&g1)

h1=(~f1&g0)+(f1&g1)

原因嘛 我分类讨论了下 发现大概是把一些0和1的情况模拟位运算过程分开处理了

注意 维护信息的时候需要有序维护 并且需要判断子树是否为空

 

分类: LCT-link cut tree

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论