专栏首页HansBug's Lab3631: [JLOI2014]松鼠的新家

3631: [JLOI2014]松鼠的新家

3631: [JLOI2014]松鼠的新家

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 707  Solved: 342

[Submit][Status][Discuss]

Description

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。

可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。

现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

Input

第一行一个整数n,表示房间个数

第二行n个整数,依次描述a1-an

接下来n-1行,每行两个整数x,y,表示标号x和y的两个房间之间有树枝相连。

Output

一共n行,第i行输出标号为i的房间至少需要放多少个糖果,才能让维尼有糖果吃。

Sample Input

5 1 4 5 3 2 1 2 2 4 2 3 4 5

Sample Output

1 2 1 2 1

HINT

2<= n <=300000

Source

题解:很明显是树链剖分!!!(HansBug:达成成就——第一棵树链剖分,get!),其实所谓的行走路径就是树链上的区间加法(呵呵呵其实这题里面由于只需要区间加最后求出各个值的和,所以连线段树都不要,干脆一个数组搞定),注意题目中说最后一个点不算,记得减去(HansBug:第一棵树链剖分,代码有点丑= =)

  1 /**************************************************************
  2     Problem: 3631
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:2660 ms
  7     Memory:48396 kb
  8 ****************************************************************/
  9  
 10 type
 11     point=^node;
 12     node=record
 13                g:longint;
 14                next:point;
 15     end;
 16 var
 17    i,j,k,l,m,n,root,tot:longint;
 18    a:array[0..300005] of point;
 19    len,son,siz,d,top,e,num,anum,f:array[0..300005] of longint;
 20    c:array[0..20,0..300005] of longint;
 21 procedure add(x,y:longint);
 22           var p:point;
 23           begin
 24                new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
 25           end;
 26 function max(x,y:longint):longint;
 27          begin
 28               if x>y then max:=x else max:=y;
 29          end;
 30 function min(x,y:longint):longint;
 31          begin
 32               if x<y then min:=x else min:=y;
 33          end;
 34 procedure swap(var x,y:longint);
 35           var z:longint;
 36           begin
 37                z:=x;x:=y;y:=z;
 38           end;
 39 procedure dfs(y,x:longint);
 40           var p:point;
 41           begin
 42                len[x]:=len[y]+1;
 43                c[0,x]:=y;son[x]:=0;
 44                siz[x]:=1;
 45                p:=a[x];
 46                while p<>nil do
 47                      begin
 48                           if p^.g<>y then
 49                              begin
 50                                   dfs(x,p^.g);
 51                                   inc(siz[x],siz[p^.g]);
 52                                   if (siz[p^.g]>siz[son[x]]) or (son[x]=0) then son[x]:=p^.g;
 53                              end;
 54                           p:=p^.next;
 55                      end;
 56           end;
 57 procedure dfs2(y,x,z:longint);
 58           var p:point;
 59           begin
 60                top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
 61                if son[x]<>0 then dfs2(x,son[x],z);p:=a[x];
 62                while p<>nil do
 63                      begin
 64                           if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
 65                           p:=p^.next;
 66                      end;
 67           end;
 68 procedure addd(x,y,z:longint);
 69           begin
 70                inc(d[x],z);
 71                dec(d[y+1],z);
 72           end;
 73 function getup(x,y:longint):longint;
 74          var i:longint;
 75          begin
 76               i:=0;
 77               while y<>0 do
 78                     begin
 79                          if odd(y) then x:=c[i,x];
 80                          inc(i);y:=y div 2;
 81                     end;
 82               exit(x);
 83          end;
 84 function getcom(x,y:longint):longint;
 85          var i:longint;
 86          begin
 87               if len[x]<len[y] then swap(x,y);
 88               x:=getup(x,len[x]-len[y]);
 89               if x=y then exit(x);
 90               for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
 91                   if c[i,x]<>c[i,y] then
 92                      begin
 93                           x:=c[i,x];
 94                           y:=c[i,y];
 95                      end;
 96               exit(c[0,x]);
 97          end;
 98 procedure treeadd(x,y:longint);
 99           var z,i:longint;
100           begin
101                z:=getcom(x,y);
102                repeat
103                      if len[top[x]]<len[z] then i:=z else i:=top[x];
104                      addd(num[i],num[x],1);
105                      if i=z then break;
106                      x:=c[0,i];
107                until false;
108                repeat
109                      if len[top[y]]<len[z] then i:=z else i:=top[y];
110                      addd(num[i],num[y],1);
111                      if i=z then break;
112                      y:=c[0,i];
113                until false;
114                addd(num[z],num[z],-1);
115           end;
116 begin
117      readln(n);
118      for i:=1 to n do read(e[i]);readln;
119      for i:=1 to n do a[i]:=nil;
120      for i:=1 to n-1 do
121          begin
122               readln(j,k);
123               add(j,k);add(k,j);
124          end;
125      fillchar(d,sizeof(d),0);
126      root:=1;dfs(0,root);
127      dfs2(0,root,root);
128      for i:=1 to trunc(round(ln(n)/ln(2)))+1 do
129          for j:=1 to n do
130              c[i,j]:=c[i-1,c[i-1,j]];
131      for i:=1 to n-1 do treeadd(e[i],e[i+1]);
132      for i:=2 to n do addd(num[e[i]],num[e[i]],-1);
133      l:=0;
134      for i:=1 to n do
135          begin
136               inc(l,d[i]);
137               f[anum[i]]:=l;
138          end;
139      for i:=1 to n do writeln(f[i]);
140      readln;
141 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用GenePred注释文件进行数据分析

    编者注:前几天在生信技能树我们发现了一个神奇的帖子(http://www.biotrainee.com/thread-928-1-1.html ), 作者用一种...

    生信技能树
  • 三只松鼠2020新财报:利润下滑都是疫情的锅?

    在某个午后,甲方的“五彩斑斓黑”要求正让你焦头烂额生无可恋,而这时,手边有一份可口零食能够帮你脱离苦海暂时快乐,岂不是美滋滋?虽然在一整包零食见底后,这种快乐也...

    刘旷
  • 松鼠AI出席Developer Week开发者大会,详解AI自适应学习平台背后的核心技术

    DeveloperWeek 是旧金山地区规模最大的开发者大会,每年吸引来自 70 多个国家的 8000+ 开发人员、工程师、软件架构师、开发团队、经理和高管聚集...

    机器之心
  • 疫情中成功“出圈”的休闲零食龙头,如何逆势创历史新高?

    受疫情影响,今年的春节快消品市场不同以往,线下销售遇冷,对于休闲零食企业来说,依然如此,而据品牌提供1-2月线上销售数据显示,却迎来小阳春。

    庄帅
  • 脑机接口创造“第六感”:激活特定神经元,大鼠训练出新感官,逃出水迷宫,像用视觉一样轻松

    宾夕法尼亚大学的科学家们,借由脑机接口,给了大鼠一种神经刺激,帮它们找到对的方向。

    量子位
  • 详解Python中pyautogui库的最全使用方法

    在使用Python做脚本的话,有两个库可以使用,一个为PyUserInput库,另一个为pyautogui库。就本人而言,我更喜欢使用pyautogui库,该库...

    砸漏
  • BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离)

    有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家...

    attack
  • AI多久可替代老师?目前已经可取代70%的传统教学工作

    前瞻产业研究院报告显示,“AI+教育”已经成为在线教育行业的关键词,到2019年中国在线教育市场规模有望达到3870亿元。

    新智元
  • 用python武装你的后院

    在知乎上看到一个问题:“可以用 Python 做哪些神奇好玩的事情?”。被赞同最多的一个回答提到了一个叫做Kurt Grandis的程序员,他用Python做了...

    Crossin先生
  • 微信智能相框来了,这次能抄底吗?

    原创2015-03-03王振 2014年智能硬件蓬勃发展,BAT、小米、 360、京东等巨头中,腾讯相对淡定,路宝盒子、QQ互联这样的“小动作”远远没有别家又做...

    罗超频道
  • SAP GUI里的收藏夹事务码管理工具

    Jerry的老家,从成都乘坐高铁只要十五分钟就能到达,所以从来不会遭受春运长途跋涉之苦。这里我提前祝愿广大SAP从业者在除夕之前,都能够平安顺利到家,和自己的亲...

    Jerry Wang
  • 2-ESP8266 SDK开发基础入门篇--点亮一个灯

    https://www.cnblogs.com/yangfengwu/p/11071580.html

    杨奉武
  • 中国公司再获KDD两项最佳:松鼠AI拿下图深度学习研讨会最佳论文&最佳学生论文

    KDD,国际数据挖掘与知识发现大会,全称:ACM SIGKDD Conference on Knowledge Discovery and DataMining...

    量子位
  • CSS3之3D魔方鼠标控制酷炫效果

    这次效果,咱们需要用JS实现。主要是监听鼠标事件,计算鼠标滑动距离,改变魔方的rotateX、rotateY

    Javanx
  • JQuery之内置函数响应事件

    今天给大家介绍一下on函数中events的种类和用法。 具体我把它分为:键盘事件,鼠标事件,input事件,还有一个是基础事件(例如:滚动,界面大小变化等等之类...

    林老师带你学编程
  • 深度剖析休闲零食的全产业链

    前瞻产业研究院近日发布报告显示,近年来,我国线上休闲食品销售规模逐年扩大,2018年为8937.80亿元,预计2022年将达到12974亿元。

    庄帅
  • 推荐一个比较好的操作鼠标键盘的python库

    最近由于在家办公,很多东西在家没法访问。 于是我想自动操作,将daily build放到teams的公司共享盘里。这样就可以在家访问了。 结果遇到了一个难题。文...

    赵云龙龙
  • 再谈BOM和DOM(7):HTML DOM Event 对象属性及DOM事件详细列表

    之前写《再谈BOM和DOM(4):HTML DOM Event 对象》时候,对event对象及各种dom事件没有详细道来,这里些表格。备查。

    周陆军
  • 小白秒变大神--windows窗口+装B神器大全 两部曲

    在现代生活中,电脑已经普及到方方面面。无论是休闲娱乐,还是上班办公,它都陪在我们身边,成为我们生活中不可分割的一部分。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券