BZOJ 3631 JLOI 2014 松鼠的新家 LCA 树链剖分
发布日期:2021-10-02 10:57:27 浏览次数:32 分类:技术文章

本文共 2679 字,大约阅读时间需要 8 分钟。

省选的day1第一题,当时不会树链剖分,手动模拟得了50分。。残念

时隔多年才会了树链剖分,重新来A这个题,感觉还是挺容易的

刚开始写树链剖分的时候注意一下从一个链跳到另一个链的时候,还有线段树的区间是否包含,刚开始学的时候总是弄不明白,画张图简单模拟一下就好了

#include 
#include
#include
#include
#define MAX 300010#define LEFT (pos << 1)#define RIGHT (pos << 1|1)using namespace std;int points;int route[MAX];int head[MAX],total;int next[MAX << 1],aim[MAX << 1];int father[MAX],size[MAX],son[MAX],deep[MAX];int top[MAX],pos[MAX],cnt;int tree[MAX << 2];inline void Add(int x,int y);inline int PreDFS(int x,int last);inline void DFS(int x,int last,int root);inline void PushDown(int pos);inline void Increase(int x,int y);inline void Modify(int l,int r,int x,int y,int pos,int num);inline int Ask(int l,int r,int aim,int pos);int main(){ cin >> points; for(int i = 1;i <= points; ++i) scanf("%d",&route[i]); for(int x,y,i = 1;i < points; ++i) { scanf("%d%d",&x,&y); Add(x,y),Add(y,x); } PreDFS(1,-1); DFS(1,-1,1); for(int i = 2;i <= points; ++i) Increase(route[i - 1],route[i]); for(int i = 1;i <= points; ++i) printf("%d\n",Ask(1,points,pos[i],1)); return 0;}inline void Add(int x,int y){ next[++total] = head[x]; aim[total] = y; head[x] = total;}inline int PreDFS(int x,int last){ deep[x] = deep[last] + 1; father[x] = last; int temp,max_size = 0; size[x] = 1; for(int i = head[x];i;i = next[i]) { if(aim[i] == last) continue; temp = PreDFS(aim[i],x); size[x] += temp; if(temp > max_size) max_size = temp,son[x] = aim[i]; } return size[x];}inline void DFS(int x,int last,int root){ pos[x] = ++cnt; top[x] = root; if(son[x]) DFS(son[x],x,root); for(int i = head[x];i;i = next[i]) { if(aim[i] == son[x] || aim[i] == last) continue; DFS(aim[i],x,aim[i]); }}inline void Increase(int x,int y){ Modify(1,points,pos[y],pos[y],1,-1); int fx = top[x],fy = top[y]; while(fx != fy) { if(deep[fx] < deep[fy]) swap(fx,fy),swap(x,y); Modify(1,points,pos[fx],pos[x],1,1); x = father[fx]; fx = top[x]; } if(deep[x] < deep[y]) swap(x,y); Modify(1,points,pos[y],pos[x],1,1);}inline void Modify(int l,int r,int x,int y,int pos,int num){ if(l == x && r == y) { tree[pos] += num; return ; } PushDown(pos); int mid = (l + r) >> 1; if(y <= mid) Modify(l,mid,x,y,LEFT,num); else if(x > mid) Modify(mid + 1,r,x,y,RIGHT,num); else { Modify(l,mid,x,mid,LEFT,num); Modify(mid + 1,r,mid + 1,y,RIGHT,num); }}inline void PushDown(int pos){ if(tree[pos]) { tree[LEFT] += tree[pos]; tree[RIGHT] += tree[pos]; tree[pos] = 0; }}inline int Ask(int l,int r,int aim,int pos){ if(l == r) return tree[pos]; PushDown(pos); int mid = (l + r) >> 1; if(aim <= mid) return Ask(l,mid,aim,LEFT); return Ask(mid + 1,r,aim,RIGHT);}
刚开始写博客啊,有博客写的不好的地方或者代码写的不好的地方欢迎指出来-_-#

转载地址:https://blog.csdn.net/jiangyuze831/article/details/38930773 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 1036 树的统计 树链剖分
下一篇:BZOJ 3630 JLOI 2013 镜面通道 最小点割集

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月03日 19时09分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

单防区扩展模块怎么用_AB罗克韦尔自动化Micro800 扩展 I/O模块型号及功能介绍 2019-04-21
java矩阵类_Java泛型——泛型矩阵类 2019-04-21
java车牌正则表达式_车牌正则表达式 2019-04-21
wordpress4.9.4 mysql_WordPress 将不再支持 PHP4 和 MySQL 4 2019-04-21
安卓是用java语言写的吗_android开发是用java语言吗? 2019-04-21
java 符号 t_java – 运算符”不能应用于’T’,’T’表示有界泛型类型 2019-04-21
用matlab写出信源熵,计算离散信源的熵matlab实现 2019-04-21
php表单yii2,Yii2创建表单(ActiveForm)方法详解 2019-04-21
php 程序授权机制,授权认证详细说明 2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令? 2019-04-21
IP/tzgm.php,LianjiaSpider/在售数量.ipynb at master · BerSerK/LianjiaSpider · GitHub 2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件 2019-04-21
linux查看系统所有变量,Linux系统各指标命令 2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢? 2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21