网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
成为超级会员,使用一键签到
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
06月01日
漏签
0
天
noip吧
关注:
25,120
贴子:
642,549
看贴
图片
吧主推荐
视频
游戏
12
回复贴,共
1
页
<<返回noip吧
>0< 加载中...
求教树的dfs序问题
只看楼主
收藏
回复
taorunz
NOI金牌
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
换根的时候,只要记录下当前的根,查询时对当前根的祖先节点特殊处理,但是换父亲怎么搞?
Yo
Enky
进队爷
13
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
难道没记录?
taorunz
NOI金牌
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
例如这样,1号是建树时的根,4号是实际的根,现在把2的父亲由3换成5,怎么搞?
1和2、3和4、4和5之间有很多节点,不能直接反过来。
sillycross
NOI铜牌
10
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
我想了一个比较囧的方法…… 不知道行不行…… DFS序时候进栈放入序列,出栈也放入序列。 这样每个结点在序列中出现两次,子树对应其根出现在序列中的两个位置为端点的区间。
这样的好处就是不用额外维护子树对应区间了…… 然后问题就简单了……
先把要砍的子树提取出来……(要么是连续一段,要么是整个序列扣掉一段)
然后插入到要拼的位置……
像3楼那种情况的话,新的dfs序子树根会变成3…… 不过无所谓,不影响查询……
具体操作的话,可以考虑用一个数组记录下来每个结点在dfs序中对应的两个splay结点…… 然后提取子树就可以直接用那两个splay结点砍出来…… 树砍出来后,查询和判断某个结点是否在子树内也可以做了……
这东西我没实现过(一般见到换根砍树就不想做了>_<)…… 只是刚才随便想的…… 很可能有错,欢迎拍砖……
taorunz
NOI金牌
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示