BZOJ 4719 [Noip2016]天天爱跑步

题目大意

给你一颗N个节点N-1条边长都为1的树，有M个人0时刻从点$S_i$出发，以每秒1单位距离的速度移动，目的地$T_i$。求每个点$X_i$时间通过的人的个数。

神题%%%

首先很轻松想到差分，将一个路径拆成一个S到LCA，之后LCA到T两个路径。

之后对于每一个点，它的答案就可以去它子树中找（它的深度+时间）为深度的点记录答案就可以了。

但是有一个问题——$LCA \to T$的路径咋统计？？？

想了1h无果= =

看了题解才明白，其实这个东西是有一个原理的——对于一个点S到LCA的路径上的点，都满足“深度+时间”为定值（时间+1深度-1）；对于LCA到T的路径上的点，都满足“深度-时间”为定值（时间+1深度+1）。之后只需要对于每一个点统计一下有没有跟它的相关值一样的点就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
int n,m,ix,iy,iz,lg[N],w[N],fa[N][20],depth[N],ans[N],ca[N],cb[N<<2];
int to[N<<3],nex[N<<3],head[N],ah[N],bh[N],tot;
inline void AE(int tx,int ty){to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}
inline void GLA(int tx,int ty){to[++tot]=ty,nex[tot]=ah[tx],ah[tx]=tot;}
inline void GLB(int tx,int ty){to[++tot]=ty,nex[tot]=bh[tx],bh[tx]=tot;}
int LCA(int tx,int ty)
{
    if(depth[tx]<depth[ty]) swap(tx,ty);
    for(int i=lg[n];~i;i--) if(depth[fa[tx][i]]>=depth[ty]) tx=fa[tx][i];
    for(int i=lg[n];~i;i--) if(fa[tx][i]!=fa[ty][i]) tx=fa[tx][i],ty=fa[ty][i];
    return tx==ty?tx:fa[tx][0];
}
void init(int pos)
{
    for(int i=1;i<=lg[n];++i) fa[pos][i]=fa[fa[pos][i-1]][i-1];
    for(int i=head[pos];i;i=nex[i]) if(!depth[to[i]])
    {
        fa[to[i]][0]=pos;
        depth[to[i]]=depth[pos]+1;
        init(to[i]);
    }
    return;
}
void DFS(int pos)
{
    ans[pos]-=ca[depth[pos]+w[pos]]+cb[w[pos]-depth[pos]+n];
    for(int i=ah[pos];i;i=nex[i]) to[i]>0?ca[to[i]]++:ca[-to[i]]--;
    for(int i=bh[pos];i;i=nex[i]) to[i]>0?cb[to[i]]++:cb[-to[i]]--;
    for(int i=head[pos];i;i=nex[i]) if(depth[to[i]]==depth[pos]+1) DFS(to[i]);
    ans[pos]+=ca[depth[pos]+w[pos]]+cb[w[pos]-depth[pos]+n];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i) scanf("%d%d",&ix,&iy),AE(ix,iy),AE(iy,ix),lg[i]=lg[i>>1]+1;
    depth[1]=1;
    init(1);
    for(int i=1;i<=n;++i) scanf("%d",w+i);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&ix,&iy),iz=LCA(ix,iy);
        GLA(ix,depth[ix]),GLA(fa[iz][0],-depth[ix]); 
        GLB(iy,n+depth[ix]-depth[iz]-depth[iz]),GLB(iz,-(n+depth[ix]-depth[iz]-depth[iz]));
    }
    DFS(1);
    for(int i=1;i<n;++i) printf("%d ",ans[i]);
    printf("%d",ans[n]);
}