洛谷P1600 天天爱跑步——树上差分

题目：https://www.luogu.org/problemnew/show/P1600

看博客：https://blog.csdn.net/clove_unique/article/details/53427248

思路好神啊...

树上差分是好东西。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=;

int n,m,head[maxn],ct,w[maxn],tp,fp,ans[maxn],f[maxn][],h[maxn],dfn[maxn],tim,a[maxn<<];

struct P{int t,pt,val;}tor[maxn<<],fr[maxn<<];

struct N{

    int to,next;

    N(int t=,int n=):to(t),next(n) {}

}edge[maxn<<];

void add(int x,int y){edge[++ct]=N(y,head[x]); head[x]=ct;}

bool cmp(P x,P y){return dfn[x.pt]<dfn[y.pt];}

void init(int x,int fa)

{

    h[x]=h[fa]+; f[x][]=fa; dfn[x]=++tim;

    for(int i=;i<=;i++)

        f[x][i]=f[f[x][i-]][i-];

    for(int i=head[x],u;i;i=edge[i].next)

        if((u=edge[i].to)!=fa)init(u,x);

}

int lca(int x,int y)

{

    if(h[x]<h[y])swap(x,y);

    int k=h[x]-h[y];

    for(int i=;i>=;i--)

        if(k&(<<i))x=f[x][i];

    for(int i=;i>=;i--)

        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    if(x==y)return x;

    return f[x][];

}

void dfs1(int x,int f)

{

    int val=w[x]+h[x],dec=a[val];

    while(tp<=(m<<) && tor[tp].pt==x) a[tor[tp].t + h[x]]+=tor[tp].val, tp++;

    for(int i=head[x],u;i;i=edge[i].next)

        if((u=edge[i].to)!=f)dfs1(u,x);

    ans[x]+=a[val]-dec;

}

void dfs2(int x,int f)

{

    int val=w[x]-h[x]+,dec=a[val];

    while(fp<=(m<<) && fr[fp].pt==x) a[fr[fp].t]+=fr[fp].val, fp++;

    for(int i=head[x],u;i;i=edge[i].next)

        if((u=edge[i].to)!=f)dfs2(u,x);

    ans[x]+=a[val]-dec;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x,y;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        add(x,y); add(y,x);

    }

    init(,);

    for(int i=;i<=n;i++)scanf("%d",&w[i]);

    for(int i=,s,t;i<=m;i++)

    {

        scanf("%d%d",&s,&t);

        int r=lca(s,t);

        tor[++tp].pt=s; tor[tp].t=; tor[tp].val=;

        if(r!=)tor[++tp].pt=f[r][], tor[tp].t=h[s]-h[r]+, tor[tp].val=-;

        fr[++fp].pt=t; fr[fp].t=h[s]-h[r]-h[r]+; fr[fp].val=;

        fr[++fp].pt=r; fr[fp].t=h[s]-h[r]-h[r]+; fr[fp].val=-;

    }

    sort(tor+,tor+tp+,cmp); tp=;

    sort(fr+,fr+fp+,cmp); fp=;

    dfs1(,);

    memset(a,,sizeof a);

    dfs2(,);

    for(int i=;i<=n;i++)printf("%d ",ans[i]);

    return ;

}