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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2924 数独挑战

2924 数独挑战  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descripti...

2953
来自专栏小樱的经验随笔

BZOJ 3668: [Noi2014]起床困难综合症【贪心】

3668: [Noi2014]起床困难综合症 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2326  So...

2784
来自专栏趣学算法

算法之美——魔鬼序列

假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永不死去……那么,由1对初生兔子开始,12个月...

702
来自专栏HansBug's Lab

2748: [HAOI2012]音量调节

2748: [HAOI2012]音量调节 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 719  Solve...

2998
来自专栏小詹同学

Python系列之六——拿什么拯救你?我的大脑

我一定是智障了,话不多说,上图上图~ ? 就是这样10个选择题,你没有看错,我一定是个智障了~佩服不用穷举,也不用参考网上的大...

3704
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

6639
来自专栏专知

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

关小刷刷题08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3 方法2 方法2:遍历数组,遇到...

2559
来自专栏专知

【 关关的刷题日记53】 Leetcode 100. Same Tree

关关的刷题日记53 – Leetcode 100. Same Tree 题目 Given two binary trees, write a function ...

3307
来自专栏JetpropelledSnake

Python Web学习笔记之递归和迭代的区别

电影故事例证: 迭代——《明日边缘》 递归——《盗梦空间》 迭代是更新变量的旧值。递归是在函数内部调用自身。 迭代是将输出做为输入,再次进行处理。比如将摄像头对...

33512
来自专栏ACM小冰成长之路

HDU-6008-Worried School

ACM模版 描述 ? 题解 简单的模拟题,题意不是特别容易翻译,但是模拟的规则十分简单,和 WFWF 晋级资格相似,大致是一共 X+Y=GX + Y = G 个...

2048

扫码关注云+社区

领取腾讯云代金券