北方火柴 @ 2017-11-06 20:02:31
var dep,num:array[0..1000000] of longint;
dp,dpn:array[0..1000000,0..25] of longint;
bucket,fir,first,u,v,next,ans,w,cotu,cotv,lth,fa,deep,f1,f2,ff1,ff2,n1,n2,nn1,nn2,p1,p2,pp1,pp2:array[-600005..600005] of longint;
power:array[0..26] of longint;
d,i,j,k,m,n,p,q,tt,lca,tm1,tm2,tm3,tm4:longint;
function qlca(a,b:longint):longint;
var l,r,i,j,tp:longint;
begin
l:=fir[a]; r:=fir[b];
if l>r then begin tp:=l; l:=r; r:=tp; end;
if l=r then exit(a);
i:=trunc(ln(r-l+1)/ln(2));
if dp[l,i]<dp[r-power[i]+1,i] then exit(num[dpn[l,i]]) else exit(num[dpn[r-power[i]+1,i]]);
end;
procedure dfs(p:longint);
var k:longint;
begin
if fir[p]=0 then fir[p]:=tt;
deep[p]:=d;
dep[tt]:=d; num[tt]:=p;
k:=first[p];
while k<>-1 do
begin
inc(d);
inc(tt);
dfs(v[k]);
dec(d);
inc(tt);
dep[tt]:=d;
num[tt]:=p;
k:=next[k];
end;
end;
procedure add1(x,y:longint);
begin
inc(tm1);
n1[tm1]:=f1[x];
f1[x]:=tm1;
p1[tm1]:=y;
end;
procedure add2(x,y:longint);
begin
inc(tm2);
n2[tm2]:=f2[x];
f2[x]:=tm2;
p2[tm2]:=y;
end;
procedure del1(p:longint);
var k:longint;
begin
k:=f1[p];
while k<>-1 do
begin
dec(bucket[deep[p1[k]]]);
k:=n1[k];
end;
end;
procedure del2(p:longint);
var k:longint;
begin
k:=f2[p];
while k<>-1 do
begin
dec(bucket[deep[p2[k]]-lth[p2[k]]]);
k:=n2[k];
end;
end;
procedure dfsu(p:longint);
var i,j,k,tp:longint;
begin
tp:=bucket[deep[p]+w[p]];
if cotu[p]>0 then inc(bucket[deep[p]],cotu[p]);
k:=ff1[p];
while k<>-1 do begin add1(pp1[k],p); k:=nn1[k]; end;
k:=first[p];
while k<>-1 do
begin
dfsu(v[k]);
k:=next[k];
end;
ans[p]:=ans[p]+bucket[deep[p]+w[p]]-tp;
del1(p);
end;
procedure dfsv(p:longint);
var i,j,k,tp:longint;
begin
tp:=bucket[deep[p]-w[p]];
if cotv[p]>0 then inc(bucket[deep[p]-lth[p]],cotv[p]);
k:=ff2[p];
while k<>-1 do begin add2(pp2[k],p); k:=nn2[k]; end;
k:=first[p];
while k<>-1 do
begin
dfsv(v[k]);
k:=next[k];
end;
del2(p);
ans[p]:=ans[p]+bucket[deep[p]-w[p]]-tp;
end;
procedure predo;
var i,j,l:longint;
begin
for i:=1 to tt do begin dp[i,0]:=dep[i]; dpn[i,0]:=i; end;
l:=trunc(ln(tt)/ln(2))+1;
for i:=1 to l do
for j:=1 to tt do
if j+power[i]<=tt then
if dp[j,i-1]<dp[j+power[i-1],i-1] then
begin
dp[j,i]:=dp[j,i-1];
dpn[j,i]:=dpn[j,i-1];
end else
begin
dp[j,i]:=dp[j+power[i-1],i-1] ;
dpn[j,i]:=dpn[j+power[i-1],i-1];
end;
end;
begin
for i:=0 to 25 do power[i]:=1 shl i;
fillchar(fir,sizeof(fir),0);
readln(n,m);
for i:=0 to n+1 do begin f1[i]:=-1; f2[i]:=-1; ff1[i]:=-1; ff2[i]:=-1; end;
for i:=0 to n+1 do first[i]:=-1;
for i:=1 to n-1 do
begin
readln(u[i],v[i]);
next[i]:=first[u[i]]; next[i]:=first[u[i]];
first[u[i]]:=i; first[u[i]]:=i;
fa[v[i]]:=u[i];
end;
tt:=1;
d:=0;
dfs(1);
predo;
for i:=1 to n do read(w[i]);
for i:=1 to m do
begin
readln(p,q);
inc(cotu[p]); inc(cotv[q]);
lca:=qlca(p,q);
lth[q]:=deep[p]+deep[q]-2*deep[lca];
inc(tm3); inc(tm4);
nn1[tm3]:=ff1[p]; ff1[p]:=tm3; pp1[tm3]:=lca;
nn2[tm4]:=ff2[q]; ff2[q]:=tm4; pp2[tm4]:=lca;
end;
dfsu(1);
fillchar(bucket,sizeof(bucket),0);
dfsv(1);
for i:=1 to n do write(ans[i],' ');
end.
//p…