3631: [JLOI2014]松鼠的新家
3631: [JLOI2014]松鼠的新家
HansBug
发布于 2018-04-11 11:06:28
发布于 2018-04-11 11:06:28
3631: [JLOI2014]松鼠的新家
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 707 Solved: 342
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.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录