首页 > 题解 > bzoj3153 Sone1

bzoj3153 Sone1

听说noip后要写个大数据结构题收收心。

于是就翻出来了这个诡异的题。

最近氪了个权限号,本来以为这是个权限题,结果还不是= =

Description

Sxyz里有一群sx。
在花老师的指导下,每周4都有一个集会活动,俗称“浇水”活动。
为了让花老师开花,这群sx都很努力地发言。
一次xbj对树很关心,总想有一道树的好题目
所以大家就开始讨论有什么树的好操作。
为了让题目变的简单,花老师开始就规定了是有根树。

何其蛙:子树修改,加一个数什么的,显然是可做的。
Dj:换根不是超开心?
Dd:什么子树min,max也不错啊。
Zzw:链上询问min也放进去吧。
Wyk: 链max当然的吧。
Xbj:如果不能换父亲就太无聊了吧。
Gy:链加。
Monkey:链上和。
Shjj:链上修改。
Wtd:子树加。
Sone: 在线就不说什么了吧…
………….

最后大家发现有这道题目有点麻烦..都懒得写,又由于sone最近被3083的遥远的国度中lct被树剖虐暴了..就担任了出题活动…….

Input

第一行是N和M,表示有这棵树有N个点M个询问
然后是N-1行,每行x,y表示x-y有一条边
接下去是N行,每行是一个数字,表示每个点的权值
后面一行表示根
接下来是M行
第一个数字是K
K=0 表示子树修改,后面x,y,表示以x为根的子树的点权值改成y
K=1 表示换根,后面x,表示把这棵树的根变成x
K=2 表示链修改,后面x,y,z,表示把这棵树中x-y的路径上点权值改成z
K=3 表示子树询问min,后面x,表示以x为根的子树中点的权值min
K=4 表示子树询问max,后面x,表示以x为根的子树中点的权值max
K=5 表示子树加,后面x,y,表示x为根的子树中点的权值+y
K=6 表示链加,后面x,y,z,表示把这棵树中x-y的路径上点权值改成+z
K=7 表示链询问min,后面x,y,表示把这棵树中x-y的路径上点的min
K=8 表示链询问max,后面x,y,表示把这棵树中x-y的路径上点的max
K=9 表示换父亲,后面x,y,表示把x的父亲换成y,如果y在x子树里不操作。
K=10 表示链询问sum,后面x,y,z,表示表示把这棵树中x-y的路径上点的sum
K=11 表示子树询问sum,后面x,表示以x为根的子树的点权sum

Output

对于每个询问输出一个答案。

Sample Input

Input1:
5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1

Input2:
10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

Sample Output

Output1:
9
1
1
Output2:
173
860
103
791
608
1557

数据范围:
N,M<=100000
中间所有的值计算在c++的int内

本来以为一个LCT就解决了,结果发现有子树??

ETT艹下试试?胡乱推了一个ETT和LCT一起更新的东西,发现复杂度还是很资瓷的,但是感觉要写几年。

然后就学了个AAA树,感觉很不错啊。。据说还是Tarjan搞的。

大概就是把lct的虚边再搞个splay记一下,新建一些节点,让虚边的点的父亲不是虚边的点,所以所有的虚边连到的点都是这个spaly的叶子。(实在是懒得画图了

这样每个点记下链的值,虚边的值,两个加起来的值,然后每个点有个val记下值,标记是a,b,表示现在的值是a*val[pos]+b。对于lct的话,开4维,0-1是链上的,2-3是连下去的虚边,单独写个东西连和断虚边。access的时候就对照着搞下就好。

最后39s卡过了。。对我交题的时候那些被卡评测的同学说声抱歉。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×