AC日记——天天爱跑步 洛谷 P1600

天天爱跑步

思路：

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

　　（伏地膜，跪烂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 ;

}