65分,为什么?

P1600 [NOIP2016 提高组] 天天爱跑步

Have_a_nice_day @ 2017-07-23 22:30:56

type
 arr=record
      pos,v,pre:longint;
     end;
var
 i,j,s,t,n,m,x,y,tot,k,roof,mark1,mark2:longint;
 obs,num,deep,point,pre,last,l,r,las1,las2:array[0..600000] of longint;
 rec1,rec2:array[0..600000] of arr;
 hash1,hash2:array[-300000..300000] of longint;
 f:array[0..300000,0..20] of longint;
procedure dfs(x:longint);
 var
  i,p:longint;
 begin
  i:=last[x];
  while i<>0 do
   begin
    p:=point[i];
    if f[x][0]<>p then
     begin
      deep[p]:=deep[x]+1;
      dfs(p);
     end;
    i:=pre[i];
   end;
 end;
procedure add(x,y:longint);
 begin
  inc(tot);
  point[tot]:=y;
  pre[tot]:=last[x];
  last[x]:=tot;
  if f[x][0]<>y then f[y][0]:=x;
 end;
function up(s,t:longint):longint;
 var
  i,l:longint;
 begin
  l:=s;
  for i:=k downto 0 do
   if (f[l][i]<>0) and (deep[f[l][i]]>=deep[t]) then l:=f[l][i];
  up:=l;
 end;
function lca(s,t:longint):longint;
 var
  i,j,a,b:longint;
 begin
  a:=s; b:=t;
  if deep[s]<deep[t] then b:=up(t,s)
   else if deep[t]<deep[s] then a:=up(s,t);
  for i:=k downto 1 do
   if (f[a][i]<>0) and (f[a][i]<>f[b][i]) then
    begin
     a:=f[a][i];
     b:=f[b][i];
    end;
  if a<>1 then a:=f[a][0];
  lca:=a;
 end;
procedure search(x:longint);
 var
  i,j,p:longint;
 begin
  dec(num[x],hash1[obs[x]+deep[x]]);
  dec(num[x],hash2[obs[x]-deep[x]]);
  i:=last[x];
  while i<>0 do
   begin
    p:=point[i];
    if f[x][0]<>p then search(p);
    i:=pre[i];
   end;
  i:=las1[x];
  while i<>0 do
   with rec1[i] do
    begin
     inc(hash1[pos],v);
     i:=pre;
    end;
  i:=las2[x];
  while i<>0 do
   with rec2[i] do
    begin
     inc(hash2[pos],v);
     i:=pre;
    end;
  inc(num[x],hash1[obs[x]+deep[x]]);
  inc(num[x],hash2[obs[x]-deep[x]]);
 end;
procedure ins1(w,p,m:longint);
 begin
  inc(mark1);
  with rec1[mark1] do
   begin
    pos:=p;
    v:=m;
    pre:=las1[w];
   end;
  las1[w]:=mark1;
 end;
procedure ins2(w,p,m:longint);
 begin
  inc(mark2);
  with rec2[mark2] do
   begin
    pos:=p;
    v:=m;
    pre:=las2[w];
   end;
  las2[w]:=mark2;
 end;
begin
 readln(n,m);
 k:=trunc(ln(n)/ln(2));
 for i:=1 to n-1 do
  begin
   readln(x,y);
   add(x,y);
   add(y,x);
  end;
 dfs(1);
 for i:=1 to k do
  for j:=1 to n do
   f[j][i]:=f[f[j][i-1]][i-1];
 for i:=1 to n do read(obs[i]);
 for i:=1 to m do
  begin
   readln(s,t);
   roof:=lca(s,t);
   ins1(s,deep[s],1);
   ins1(f[roof][0],deep[s],-1);
   ins2(t,deep[s]-2*deep[roof],1);
   ins2(roof,deep[s]-2*deep[roof],-1);
  end;
 search(1);
 for i:=1 to n do write(num[i],' ');
end.

|