wang_sj @ 2017-01-21 10:14:43
var
sum,ans,head,ret,next,w,deep,st,ed,father,head1,ret1,next1,head2,ret2,next2,len2,head3,ret3,next3,len3:array[-1..1000011] of longint;
fa:array[0..300011,0..20] of longint;
flag:array[0..600000] of boolean;
a:array[-2000000..2000000] of longint;
tot,i,n,m,u,v,tot1,tot2,tot3:longint;
procedure ins(u,v:longint);
begin
tot:=tot+1;
ret[tot]:=v;
next[tot]:=head[u];
head[u]:=tot;
end;
procedure find(u,pre:longint);
var
i,v:longint;
begin
deep[u]:=deep[pre]+1;
fa[u,0]:=pre;
i:=head[u];
while i<>0 do
begin
v:=ret[i];
if v<>pre then
find(v,u);
i:=next[i];
end;
end;
procedure build;
var
i,k:longint;
begin
for k:=1 to 20 do
for i:=1 to n do
fa[i,k]:=fa[fa[i,k-1],k-1];
end;
function lca(a,b:longint):longint;
var
i,t:longint;
begin
if deep[a]<deep[b] then begin t:=a;a:=b;b:=t; end;
for i:=20 downto 0 do
if deep[a]-1<<i>=deep[b] then a:=fa[a,i];
if a=b then exit(a);
for i:=20 downto 0 do
if fa[a,i]<>fa[b,i] then
begin
a:=fa[a,i];
b:=fa[b,i];
end;
exit(fa[a,0]);
end;
procedure ins1(u,v:longint);
begin
tot1:=tot1+1;
ret1[tot1]:=v;
next1[tot1]:=head1[u];
head1[u]:=tot1;
end;
procedure ins2(u,v,l:longint);
begin
tot2:=tot2+1;
ret2[tot2]:=v;
len2[tot2]:=l;
next2[tot2]:=head2[u];
head2[u]:=tot2;
end;
procedure ins3(u,v,l:longint);
begin
tot3:=tot3+1;
ret3[tot3]:=v;
len3[tot3]:=l;
next3[tot3]:=head3[u];
head3[u]:=tot3;
end;
procedure dfs_up(u,pre:longint);
var
i,v,mark:longint;
begin
i:=head[u];
mark:=a[deep[u]+w[u]];
while i<>0 do
begin
v:=ret[i];
if v<>pre then
dfs_up(v,u);
i:=next[i];
end;
if flag[u] then a[deep[u]]:=a[deep[u]]+sum[u];
flag[u]:=false;
ans[u]:=a[deep[u]+w[u]]-mark;
i:=head1[u];
while i<>0 do
begin
v:=ret1[i];
a[deep[v]]:=a[deep[v]]-1;
if deep[u]+w[u]=deep[v] then ans[u]:=ans[u]-1;
i:=next1[i];
end;
end;
procedure dfs_down(u,pre:longint);
var
i,v,mark:longint;
begin
i:=head[u];
mark:=a[deep[u]-w[u]];
while i<>0 do
begin
v:=ret[i];
if v<>pre then
dfs_down(v,u);
i:=next[i];
end;
if flag[u] then
begin
i:=head3[u];
while i<>0 do
begin
v:=ret3[i];
a[deep[u]-len3[i]]:=a[deep[u]-len3[i]]+1;
i:=next3[i];
end;
end;
flag[u]:=false;
ans[u]:=a[deep[u]-w[u]]-mark+ans[u];
i:=head2[u];
while i<>0 do
begin
v:=ret2[i];
a[deep[v]-len2[i]]:=a[deep[v]-len2[i]]-1;
i:=next2[i];
end;
end;
begin
readln(n,m);
for i:=1 to n-1 do
begin
readln(u,v);
ins(u,v);
ins(v,u);
end;
for i:=1 to n do
read(w[i]);
readln;
find(1,-1);
build;
for i:=1 to m do
begin
readln(st[i],ed[i]);
father[i]:=lca(st[i],ed[i]);
ins1(father[i],st[i]);
ins2(father[i],ed[i],deep[st[i]]+deep[ed[i]]-2*deep[father[i]]);
ins3(ed[i],father[i],deep[st[i]]+deep[ed[i]]-2*deep[father[i]]);
end;
for i:=1 to m do
begin
flag[st[i]]:=true;
sum[st[i]]:=sum[st[i]]+1;
end;
dfs_up(1,-1);
for i:=1 to m do
flag[ed[i]]:=true;
fillchar(a,sizeof(a),0);
dfs_down(1,-1);
for i:=1 to n do
write(ans[i],' ');
end.
by Alextokc @ 2017-02-06 21:42:09
多半都是数组问题。。。
pascal...