记录编号	471571	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	4.238 s
提交时间	2017-11-06 17:25:51	内存使用	158.25 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=300000+10;
#define mem(a) memset(a,0,sizeof(a))
int n,m,cnt,num,dfn;
int head[2*M],dep[M],in[M],out[M],tim[M],ans[M],fa[M][22];
int sum[25*M],lc[25*M],rc[25*M],root[25*M];
struct DATE{int fr,to,last;}date[2*M];
struct P{int s,t,lca;}p[M];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int x,int y){
    date[++num]=(DATE){x,y,head[x]};
    head[x]=num;
}
void dfs(int x){
    in[x]=++dfn;
    for(int i=1;(1<<i)<=dep[x];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=date[i].last){
        int to=date[i].to;
        if(to!=fa[x][0]){
            fa[to][0]=x;
            dep[to]=dep[x]+1;
            dfs(to);
        }
    }out[x]=dfn;
}
inline int getlca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void update(int pos,int zhi,int &rt,int l,int r){
    if(!pos)  return ;
    if(!rt) rt=++cnt;
    sum[rt]+=zhi;
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) update(pos,zhi,lc[rt],l,mid);
    else         update(pos,zhi,rc[rt],mid+1,r);
}
int query(int s,int t,int &rt,int l,int r){
    if(!rt) return 0;
    if(s<=l&&r<=t) return sum[rt];
    int mid=l+r>>1; int res=0;
    if(s<=mid) res+=query(s,t,lc[rt],l,mid);
    if(t>mid) res+=query(s,t,rc[rt],mid+1,r);
    return res;
}
int main(){
    freopen("runninga.in","r",stdin);
    freopen("runninga.out","w",stdout);
    n=read();m=read();int aa,bb;
    for(int i=1;i<n;i++){
        aa=read();bb=read();
        add(aa,bb);add(bb,aa);
    } dep[1]=1;dfs(1);
    for(int i=1;i<=n;i++) tim[i]=read();
    for(int i=1;i<=m;i++){
        p[i].s=read();p[i].t=read();
        p[i].lca=getlca(p[i].s,p[i].t);
    }
    for(int i=1;i<=m;i++){
        update(in[p[i].s],1,root[dep[p[i].s]],1,n);
        update(in[fa[p[i].lca][0]],-1,root[dep[p[i].s]],1,n);
    }
    for(int i=1;i<=n;i++)
        ans[i]+=query(in[i],out[i],root[dep[i]+tim[i]],1,n);
    cnt=0;mem(sum);mem(root);mem(lc);mem(rc);
    for(int i=1;i<=m;i++){
        int d=(dep[p[i].s]-(dep[p[i].lca]<<1)+500000);
        update(in[p[i].t],1,root[d],1,n);
        update(in[p[i].lca],-1,root[d],1,n);
    }
    for(int i=1;i<=n;i++)
        ans[i]+=query(in[i],out[i],root[tim[i]-dep[i]+500000],1,n);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}