1A此题暴祭
(下面记点(x)深度为(de_x),某个时间点记为(w_x))
首先,每条路径是可以拆成往上和往下两条路径的
对于往上的路径,假设有个人往上跑,(w_y)在点(y),那么如果能对点(x)的观察员产生贡献,当且仅当(w_x+de_x=w_y+de_y)
对于往下的路径,假设有个人往下跑,(w_y)在点(y),那么如果能对点(x)的观察员产生贡献,当且仅当(w_x-de_x=w_y-de_y)
所以对于每个点开两个线段树,每个下表存(w_x+de_x)或(w_x-de_x)的点的个数,对于每条路径(x,y),记(len)为路径长度(结束时间点),(mid)为到达(lca)的时间,在(x)的第一个线段树的(de_x)处+1,在(lca)的第一个线段树的(mid+de_{lca})处-1,在y的第二个线段树的(len-de_y+n)处+1,在(fa_{lca})的第二个线段树的(mid-1-de_{fa_{lca}}+n)处-1(不能出现负下标).dfs整棵树,把(x)所有儿子的线段树并起来,然后这个点的答案就是第一棵线段树的(w_x+de_x)加第二棵线段树的(w_x-de_x+n)的值
我太傻了,这两颗线段树可以分开处理的,我放在一起处理了,空间爆炸,bzoj就过不去了qwq
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define eps (1e-5)
using namespace std;
const int N=300000+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int n,m,w[N],an[N],fa[N],sz[N],de[N],son[N],top[N];
void dfs1(int x)
{
sz[x]=1;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]) continue;
fa[y]=x,de[y]=de[x]+1,dfs1(y),sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}
void dfs2(int x,int ntp)
{
top[x]=ntp;
if(son[x]) dfs2(son[x],ntp);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
il int glca(int x,int y)
{
while(top[x]!=top[y])
{
if(de[top[x]]<de[top[y]]) swap(x,y);
x=fa[top[x]];
}
return de[x]<de[y]?x:y;
}
struct sgtree
{
int s[(N*3)*20],ch[(N*3)*20][2],rt[N],tt;
sgtree(){tt=0;}
il void inst(int o1,int o2,int x,int dt)
{
int l=1,r=n+n;
s[o1]=s[o2]+dt;
while(l<r)
{
int mid=(l+r)>>1;
if(x<=mid)
{
ch[o1][0]=++tt,ch[o1][1]=ch[o2][1];
o1=ch[o1][0],o2=ch[o2][0];
r=mid;
}
else
{
ch[o1][0]=ch[o2][0],ch[o1][1]=++tt;
o1=ch[o1][1],o2=ch[o2][1];
l=mid+1;
}
s[o1]=s[o2]+dt;
}
}
int merge(int o1,int o2)
{
if(!o1||!o2) return o1+o2;
int o=++tt;
s[o]=s[o1]+s[o2];
ch[o][0]=merge(ch[o1][0],ch[o2][0]);
ch[o][1]=merge(ch[o1][1],ch[o2][1]);
return o;
}
int quer(int o,int l,int r,int lx)
{
if(!o) return 0;
if(l==r) return s[o];
int mid=(l+r)>>1;
if(lx<=mid) return quer(ch[o][0],l,mid,lx);
else return quer(ch[o][1],mid+1,r,lx);
}
}S,T;
il void dfs3(int x)
{
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]) continue;
dfs3(y),S.rt[x]=S.merge(S.rt[x],S.rt[y]),T.rt[x]=T.merge(T.rt[x],T.rt[y]);
}
an[x]=S.quer(S.rt[x],1,n+n,w[x]+de[x])+T.quer(T.rt[x],1,n+n,w[x]-de[x]+n);
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<n;i++) add(rd(),rd());
de[1]=1,dfs1(1),dfs2(1,1);
for(int i=1;i<=n;i++) w[i]=rd();
while(m--)
{
int x=rd(),y=rd(),lca=glca(x,y),lth=de[x]+de[y]-(de[lca]<<1),mid=lth-de[y]+de[lca],la;
la=S.rt[x],S.rt[x]=++S.tt,S.inst(S.rt[x],la,de[x],1);
la=S.rt[lca],S.rt[lca]=++S.tt,S.inst(S.rt[lca],la,de[lca]+mid,-1);
la=T.rt[y],T.rt[y]=++T.tt,T.inst(T.rt[y],la,lth-de[y]+n,1);
la=T.rt[fa[lca]],T.rt[fa[lca]]=++T.tt,T.inst(T.rt[fa[lca]],la,mid-1-de[fa[lca]]+n,-1);
}
dfs3(1);
for(int i=1;i<=n;i++) printf("%d ",an[i]);
return 0;
}