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.