天天爱跑步

思路:

  树上差分+分层动态线段树;

  (伏地膜,跪烂xxy)

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 300005
#define maxtot maxn*19
int n,m,deep[maxn],top[maxn],size[maxn];
int f[maxn],cnt,head[maxn],E[maxn<<],V[maxn<<];
int watch[maxn],st[maxn],en[maxn],tot,Count,ans[maxn];
int lc[maxtot],rc[maxtot],dis[maxtot],lar[maxn];
int lca[maxn],id[maxn],root[maxn*],li[maxn],ri[maxn];
inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
}
void dfs1(int now,int fa)
{
size[now]=,f[now]=fa;
deep[now]=deep[fa]+;
for(int i=head[now];i;i=E[i])
{
if(V[i]==f[now]) continue;
dfs1(V[i],now),size[now]+=size[V[i]];
if(size[V[i]]>size[lar[now]]) lar[now]=V[i];
}
}
void dfs2(int now,int chain)
{
top[now]=chain,id[now]=++cnt,li[now]=cnt;
if(lar[now]) dfs2(lar[now],chain);
else
{
ri[now]=cnt;
return;
}
for(int i=head[now];i;i=E[i])
{
if(V[i]==f[now]||V[i]==lar[now]) continue;
dfs2(V[i],V[i]);
}
ri[now]=cnt;
}
inline int find(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
return x;
}
void updata(int &now,int l,int r,int to,int x)
{
if(!to) return;
if(!now) now=++tot;
dis[now]+=x;
if(l==r) return;
int mid=l+r>>;
if(to<=mid) updata(lc[now],l,mid,to,x);
else updata(rc[now],mid+,r,to,x);
}
void query(int now,int l,int r,int tl,int tr)
{
if(!now) return;
if(l>=tl&&r<=tr)
{
Count+=dis[now];
return;
}
int mid=l+r>>;
if(tl<=mid) query(lc[now],l,mid,tl,tr);
if(tr>mid) query(rc[now],mid+,r,tl,tr);
}
int main()
{
in(n),in(m);int u,v,pos;
for(int i=;i<n;i++)
{
in(u),in(v);
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
cnt=,dfs1(,),cnt=,dfs2(,);
for(int i=;i<=n;i++) in(watch[i]);
for(int i=;i<=m;i++)
{
in(st[i]),in(en[i]);
lca[i]=find(st[i],en[i]);
updata(root[deep[st[i]]],,n,id[st[i]],);
updata(root[deep[st[i]]],,n,id[f[lca[i]]],-);
}
for(int i=;i<=n;i++)
{
Count=;
query(root[deep[i]+watch[i]],,n,li[i],ri[i]);
ans[i]=Count;
}
memset(rc,,sizeof(rc));
memset(lc,,sizeof(lc));
memset(dis,,sizeof(dis));
memset(root,,sizeof(root));
tot=;
for(int i=;i<=m;i++)
{
pos=deep[st[i]]-deep[lca[i]]*+n*;
updata(root[pos],,n,id[en[i]],);
updata(root[pos],,n,id[lca[i]],-);
}
for(int i=;i<=n;i++)
{
Count=;
query(root[watch[i]-deep[i]+n*],,n,li[i],ri[i]);
ans[i]+=Count;
}
for(int i=;i<=n;i++) printf("%d ",ans[i]);
return ;
}
05-11 21:43