Posts match “ 数据结构 ” tag:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=509&page=show_problem&problem=4225

思路:离线+逆序操作。逆序后删边变连边,用并查集判连通性即可。Q操作用名次树解决,C操作拆为删除和插入两个操作。
顺便附上我的Treap+名次树模板。

继续阅读

http://codeforces.com/contest/343

前三题水题。

D题
利用一个重要性质即可秒:若一颗子树的某个节点为空,那么其父节点也为空。
首先dfs一下弄出时间戳,然后用一个set维护空节点。
2号操作直接把节点v插到set中。
1号操作先看看以当前节点的父亲为根的子树是否含有空节点,有则把父亲插入到set中。
3号操作,看当前节点及后代中有没有空节点即可。

代码:

继续阅读