洛谷P3258松鼠的新家

　　题目传送门

　　恩，很明显的一个树剖题，配合树上差分其实也并不难，不过无奈蒟蒻树剖还没那么熟练，而且树上差分也做的少，所以这题愣是做了一中午。。。。。。唉，果然我还是太菜了。恩，具体做法在代码中解释吧：

　　

//It is made by HolseLee on 6th Jan 2018
//luogu.org
#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int N=;

int n,a[N],c[N],ans[N],head[N],cnt;

int sum,hson[N],size[N],fa[N],id;

int depth[N],top[N],dfn[N],xu[N];

struct Node{

  int to,next;

}edge[N<<];

inline int read()//快读

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

inline void add(int x,int y)//加边

{

  edge[++cnt].to=y;

  edge[cnt].next=head[x];

  head[x]=cnt;

}
//两个dfs，树剖套路，不解释

inline void dfs1(int u)

{

  size[u]=;

  for(int i=head[u];i!=-;i=edge[i].next){

    int v=edge[i].to;

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

    depth[v]=depth[u]+;fa[v]=u;

    dfs1(v);size[u]+=size[v];

    if(!hson[u]||size[v]>size[hson[u]])

      hson[u]=v;

  }

}

inline void dfs2(int u,int nowtop)

{

  dfn[u]=++id;xu[id]=u;top[u]=nowtop;

  if(hson[u])dfs2(hson[u],nowtop);

  for(int i=head[u];i!=-;i=edge[i].next){

    int v=edge[i].to;

    if(v==fa[u]||v==hson[u])continue;

    dfs2(v,v);}

}

inline void lca(int x,int y)//求lca
{

  int fax=top[x],fay=top[y];

  while(fax!=fay){

    if(depth[fax]<depth[fay])

      {swap(fax,fay);swap(x,y);}

    c[dfn[fax]]++;c[dfn[x]+]--;
　　 //在深度较浅的点++，较深的点--，差分

    x=fa[fax];fax=top[x];

  }

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

  c[dfn[y]]++;c[dfn[x]+]--;
　　　//同上

}

void ready()

{

  memset(head,-,sizeof(head));

  n=read();

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

    a[i]=read();

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

    int x=read();int y=read();

    add(x,y);add(y,x);}
　　//加边，这里不需要用a数组
　　//从样例分析就可以知道，加边的序号是房间原本的编号

  depth[]=;fa[]=;

  dfs1();dfs2(,);

}

void work()

{

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

    int x=a[i],y=a[i+];

    lca(x,y);//对每一条路径的起点终点进行操作

    c[dfn[y]]--;c[dfn[y]+]++;

  }

  sum=;

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

    sum+=c[i];

    ans[xu[i]]=sum;
　　//记录结果，这里注意，不能直接记录ans[i];
　　//要用到xu数组;

  }

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

    printf("%d\n",ans[i]);
　　//输出，完结

  return;

}

int main()

{

  ready();

  work();

  return ;

}

　　总的来说，这是一道用来练习树剖和树上差分的好题。