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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

差分

一开始竟然想分情况讨论来差分，然后发现各自情况要分析，就是为了解决中间节点重复计算的问题，结果最后一想，中间重复计算了一次，那我最后减掉不就好了么，，，那这就是一道差分裸题了（这是唯一不同的地方）

由于是树上差分，所以要先求出所有需要的LCA，然后就是树上差分的套路了

这里由于进来后再出去是只能算一次的，所以略有不同，但实际上也不麻烦，因为直接维护是很困难的，所以不如不维护这个地方，直接在统计答案的时候减掉这些多出来的。

 using namespace std;

 #define R register int

 #define AC 300100

 #define D printf("line in %d\n",__LINE__);

 int n,cnt;//cnt是计LCA的

 int date[AC*],Next[AC*],Head[AC],tot=;//存图

 int qdate[AC*],qNext[AC*],qHead[AC],qtot=;//存询问

 int LCA[AC],ans[AC*];//直接按顺序求，所以线性顺序即可

 int father[AC],t[AC],power[AC],fa[AC];

 bool vis[AC];

 //error!!!前向星因为是双向边，然后询问也是双向的，所以这些数组都要*2啊！！！

 inline int read()

 {

     int x=;char c;

     while(isspace(c=getchar()));

     while(c>='' && c<='')x=x*+c-'',c=getchar();

     return x;

 }

 void add1(int f,int w)//加图

 {

     date[++tot]=w,Next[tot]=Head[f],Head[f]=tot;

     date[++tot]=f,Next[tot]=Head[w],Head[w]=tot;

 }

 int find(int x)

 {

     if(father[x]==x)    return x;

     else return father[x]=find(father[x]);

 }

 void add2(int f,int w)//加询问

 {

     qdate[++qtot]=w,qNext[qtot]=qHead[f],qHead[f]=qtot;

     qdate[++qtot]=f,qNext[qtot]=qHead[w],qHead[w]=qtot;

 }

 void DFS(int x)

 {

     R now;

     vis[x]=true;

     for(R i=Head[x]; i ;i=Next[i])

     {

         now=date[i];

         if(!vis[now])

         {

             DFS(now);

             father[now]=x;//访问完所有的字节点后接上来

         }

         else fa[x]=now;//不然就是父亲，因为是点权，所以直接等于now就好了

     }

     for(R i=qHead[x]; i ;i=qNext[i])

     {

         now=qdate[i];

         if(vis[now] && !ans[i ^ ])ans[i]=find(now);

     }

 }

 void pre()

 {

     R a,b;

     n=read();

     for(R i=;i<=n;i++)  t[i]=read();

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

     {

         a=read(),b=read();

         add1(a,b);

     }

     for(R i=;i<n;i++)//添加询问

         add2(t[i],t[i+]);

     for(R i=;i<=n;i++)father[i]=i;

     DFS();

     for(R i=;i<=n*+;i++)

         if(ans[i])  LCA[++cnt]=ans[i];

 }

 void getans(int x)//统计答案,可以统计进入

 {

     R now;

     for(R i=Head[x]; i ;i=Next[i])

     {

         now=date[i];

         if(now!=fa[x])

         {

             getans(now);

             power[x]+=power[now];

         }

     }

 }

 void work()

 {

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

     {

         power[t[i]]++,power[t[i+]]++,power[LCA[i]]--,power[fa[LCA[i]]]--;//由于题目特殊性，不能每次都+1,因为进出房间只是一次

     }//但是这样并不好计算，那完全可以直接像平常一样统计啊，由于这样每个中间节点都会被重复计算一次，那输出的时候-1不就好了吗

     getans();

     for(R i=;i<=n;i++)//因为要按下标输出，但是重复计算的是序列中间的，所以是要序列中间都-1,所以先处理

         power[t[i]]--;

     for(R i=;i<=n;i++)  printf("%d\n",power[i]);

 }

 int main()

 {

     freopen("in.in","r",stdin);

     pre();

     work();

     fclose(stdin);

     return ;

 }