开发工具:
文件大小: 4kb
下载次数: 0
上传时间: 2018-08-08
详细说明: 预处理 第一遍dfs求出树每个结点的深度deep[x],其为根的子树大小size[x] 以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先 第二遍dfs 根节点为起点,向下拓展构建重链 选择最大的一个子树的根继承当前重链 其余节点,都以该节点为起点向下重新拉一条重链 给每个结点分配一个位置编号,每条重链就相当于一段区间,用数据结构去维护。 把所有的重链首尾相接,放到同一个数据结构上,然后维护这一个整体即可 修改操作 1、单独修改一个点的权值 根据其编号直接在数据结构中修改就行了。 2、修改点u和点v的路径上的权值 (1)若u和v在同一条重链上 直接用数据结构修改pos[u]至pos[v]间的值。 (2)若u和v不在同一条重链上 一边进行修改,一边将u和v往同一条重链上靠,然后就变成了情况(1)。 伪代码 CHANGE (x, y ,d) while top[x]≠top[y] do if dep[top[x]]dep[y] then SWAP ( x,y) CHANGE-IT(tid[x],tid[y],d) //CHANGE-IT(l,r,d)为数据结构的修改操作:将区间[l,r]上的所有权值改为d 查询操作 查询操作的分析过程同修改操作 伪代码 QUERY (x, y) while top[x]≠top[y] do if dep[top[x]]dep[y] then SWAP (x,y) QUERY-IT(tid[x],tid[y]) //QUERY-IT(l,r)为数据结构的查询操作, 题目不同,选用不同的数据结构来维护值,通常有线段树和splay [2] ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度。
- 本站已设置防盗链,请勿用迅雷、QQ旋风等多线程下载软件下载资源,下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
- 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.