bzoj3631 [JLOI2014]松鼠的新家——树上差分

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3631

树上差分；注意路径的结尾被多算了一次，最后要减去(不能提前减)。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=;

int n,a[maxn],head[maxn],ct,f[maxn],re[maxn],fa[maxn][],bin[],deep[maxn];

struct N{

    int to,next;

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

}edge[maxn<<];

bool vis[maxn];

void dfs(int x)

{

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

    {

        if(deep[x]>=bin[i])fa[x][i]=fa[fa[x][i-]][i-];

        else break;

    }

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

    {

        if(edge[i].to==fa[x][])continue;

        deep[u=edge[i].to]=deep[x]+;

        fa[u][]=x;

        dfs(u);

    }

}

int lca(int x,int y)

{

    if(deep[x]>deep[y])swap(x,y);

    int t=deep[y]-deep[x];

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

        if(t&bin[i])y=fa[y][i];

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

        if(fa[x][i]!=fa[y][i])

            x=fa[x][i],y=fa[y][i];

    if(x==y)return y;

    return fa[y][];

}

void dfs2(int x)

{

//    cout<<x<<endl;

    if(vis[x])return;

    vis[x]=;

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

    {

        u=edge[i].to;

        if(u==fa[x][])continue;

        dfs2(u);

        f[x]+=f[u];

    }

}

int main()

{

    bin[]=;

    for(int i=;i<;i++)bin[i]=(bin[i-]<<);

    scanf("%d",&n);

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

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

    {

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

        edge[++ct]=N(y,head[x]);head[x]=ct;

        edge[++ct]=N(x,head[y]);head[y]=ct;

    }

    dfs();

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

    {

        f[a[i-]]++;f[a[i]]++;re[a[i]]++;

        int l=lca(a[i-],a[i]);

        f[l]--;f[fa[l][]]--;

    }

    dfs2();

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

        printf("%d\n",f[i]-re[i]);

    return ;

}