首页 > 代码库 > [NOIP2016-day1-T2]天天爱跑步running_题解
[NOIP2016-day1-T2]天天爱跑步running_题解
题目来源：http://www.lydsy.com/JudgeOnline/problem.php?id=4719
镇楼图：
noip滚粗后、、订正的第一题。
题目大意：
有若干条路径在一棵树上，问每个点恰为多少条路径起点出发Ti长度处。
解题方略：
这题可以O(n)。。结果shy非常有趣地在考场上码80分暴力、结果还爆QAQ（这题，80分做法，比100分做法难吧。。）
考虑把询问分成不同的两个链。但是，如果有链的话，就不可避免要树剖（就是因为他不像联赛算法，shy考试时才没写QWQ）。然而其实不必。利用DFS的性质，可以知道，在一个点打标记，可以影响到它的子树（相对地，也可以是所有父亲）。那么，我们考虑暴力，就是询问每个点x，子树里有多少个d[u]=d[x]+t[x]或d[v]-len[u,v]=d[x]-t[x]，复杂度O(n*子树大小)。那么，这个只要一个桶就可以记录。求LCA只要tarjan离线就可以O(n+m)，这里暂时把并查集的复杂度也看成常数倍。那么，有些人就会卡在子树的合并上。其实并不用合并。因为，一个点退出时，我们即知，其子树的操作都已经实施过（添加/删除），那么，我们只需在进入时算一遍Ans、退出时算一遍Ans，两者的差就是子树的贡献。
AC代码：
这里bzoj之前数据有漏导致WA了，事情咋那么多呢TAT。
1 {$M 100000000,0,100000000} 2 type 3 Chitose=record 4 e:longint; 5 head :array[0..300005]of longint; 6 next,node:array[0..600005]of longint 7 end; 8 Chitoge=array[-600005..600005]of longint; 9 var 10 n,m,i,u,v:longint; 11 t,d,z,s,Ans:array[0..300005]of longint; 12 p,q:Chitoge; 13 o,a:Chitose; 14 f,g:array[0..1]of Chitose; 15 16 procedure ad(var x:Chitose;u,v:longint); 17 begin 18 with x do 19 begin 20 inc(e); 21 next[e]:=head[u]; 22 head[u]:=e; 23 node[e]:=v 24 end 25 end; 26 27 function fd(x:longint):longint; 28 begin if x<>z[x] then z[x]:=fd(z[x]); exit(z[x]) end; 29 30 procedure sk(u:longint); 31 var i,v,w,x,y,c:longint; 32 begin 33 z[u]:=u; 34 i:=o.head[u]; 35 while i<>0 do 36 begin 37 v:=o.node[i]; 38 if d[v]=0 then begin d[v]:=d[u]+1; sk(v); z[v]:=u end; 39 i:=o.next[i] 40 end; 41 i:=a.head[u]; 42 while i<>0 do 43 begin 44 w:=a.node[i]>>1; 45 if s[w]=0 then s[w]:=u 46 else begin v:=s[w]; 47 c:=fd(v); 48 s[w]:=d[v]+d[u]-2*d[c]; 49 if odd(a.node[i]) then begin x:=v; y:=u end 50 else begin x:=u; y:=v end; 51 ad(f[0],x,d[x]); 52 ad(f[1],c,d[x]); 53 ad(g[0],y,d[y]-s[w]); 54 ad(g[1],c,d[y]-s[w]) end; 55 i:=a.next[i] 56 end 57 end; 58 59 procedure __Claris(u:longint); 60 var i,v:longint; 61 begin 62 z[u]:=0; 63 Ans[u]:=p[d[u]+t[u]]+q[d[u]-t[u]]; 64 i:=f[0].head[u]; while i<>0 do begin inc(p[f[0].node[i]]); i:=f[0].next[i] end; 65 i:=g[0].head[u]; while i<>0 do begin inc(q[g[0].node[i]]); i:=g[0].next[i] end; 66 i:=o.head[u]; 67 while i<>0 do 68 begin 69 v:=o.node[i]; 70 if z[v]<>0 then __Claris(v); 71 i:=o.next[i] 72 end; 73 i:=f[1].head[u]; while i<>0 do begin dec(p[f[1].node[i]]); i:=f[1].next[i] end; Ans[u]:=p[d[u]+t[u]]+q[d[u]-t[u]]-Ans[u]; 74 i:=g[1].head[u]; while i<>0 do begin dec(q[g[1].node[i]]); i:=g[1].next[i] end; 75 end; 76 77 begin 78 read(n,m); 79 for i:=2 to n do 80 begin 81 read(u,v); 82 ad(o,u,v); 83 ad(o,v,u) 84 end; 85 for i:=1 to n do read(t[i]); 86 for i:=1 to m do 87 begin 88 read(u,v); 89 ad(a,u,i<<1); 90 ad(a,v,i<<1+1) 91 end; 92 d[1]:=1; 93 sk(1); 94 __Claris(1); 95 write(Ans[1]); for i:=2 to n do write(‘ ‘,Ans[i]) 96 end.
[NOIP2016-day1-T2]天天爱跑步running_题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。