Peter_Matthew的博客

题解 T53818 【[退役欢乐赛Day2T3]谁是退役的人】

2018-10-26

LuoguT53818:

Splay?Rotate?不不不!这些都是蒟蒻出题人吓唬做题人的道具而已。

实际上 rotate 操作在这里起到的作用等价于将节点的父节点染为相同颜色。原因就是在rotate(x)之后,x 的原父节点 y 的另一个儿子变成了 x 的后代,而 y 变成了 x 的后代。然后它们都被重新染色。而且这种染色对于其他的子树没有任何影响。

学习子树被覆盖只需判断其祖先们有一个被覆盖。当然,由于数据范围过小,所以也可以遍历子树进行赋值。而对于另一种情况,可以打标记啊什么的,但是我不会写……而且数据太小,所以每次就暴力染色即可。

首先要维护好一棵树的基本信息,比如深度和子树大小什么的。

直接写三个人三棵树可能会比较难受,所以可以先写一个人一棵树,然后把数组加一维得到三个人三棵树的写法。


如果不知道世界最强OI教练的英文首字母缩写大写,可以查看博客的友链。

本题By:asdfghjkl123

标签: 题解
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章