树链剖分 [JLOI2014]松鼠的新家

[JLOI2014]松鼠的新家

时间限制: 1 Sec 内存限制: 128 MB

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。

可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。

现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入

第一行一个整数n，表示房间个数

第二行n个整数，依次描述a1-an

接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

输出

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

样例输入

样例输出

提示

2<= n <=300000

　　树链剖分裸题，全当复习了。

　　首先既然是在树上，那么两点之间的路径就是唯一的了，果断树剖，其实LCA也可以，不过时间复杂度貌似并不允许，所以放弃。

　　首先，可以明确的是，我们直接从a[1]点位出发一定是最优的，不知道Q某犇为啥会纠结这个，然后就是慢慢慢慢的树剖了，然后就是一两个坑点，首先，虽然每一次树剖都是从a[i]~a[i+1]，但a[i]早在求a[i-1]~a[i]时算过了，所以当我们最后输出的时候一定要记得把a[2~n]的结果-1。为什么要把a[n]的结果也减一呢？读题，a[n]是餐厅，因此不必放糖，但这并不意味着来回经过不必放糖，所以在最后一起减掉就好了。

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 #include<queue>

 #include<string>

 #include<cmath>

 # define N

 using namespace std;

 int n;

 int b[],a[];

 struct ro{

     int to;

     int next;

 }road[];

 int zz;

 void build(int x,int y){

     zz++;

     road[zz].to=y;

     road[zz].next=a[x];

     a[x]=zz;

 }

 int deep[N],fa[N],hson[N],size[N];

 void dfs(int x,int dep){

     deep[x]=dep;

     size[x]=;

     for(int i=a[x];i>;i=road[i].next)

     {

         int y=road[i].to;

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

         fa[y]=x;

         dfs(y,dep+);

         size[x]+=size[y];

         if(size[hson[x]]<size[y])

             hson[x]=y;

     }

 }

 int zz2;

 int f2[N],dl[N],dfn[N];

 void dfs2(int x,int top){

     f2[x]=top;

     zz2++;

     dl[zz2]=x;

     dfn[x]=zz2;

     if(hson[x]) dfs2(hson[x],top);

     for(int i=a[x];i>;i=road[i].next)

     {

         int y=road[i].to;

         if(y==fa[x]||y==hson[x]) continue;

         dfs2(y,y);

     }

 }

 struct no{

     int sum;

     int lazy;

     int right,left;

     int mid;

 }node[*N];

 void build(int left,int right,int x){

     node[x].left=left;

     node[x].right=right;

     if(left==right)

     {

         return;

     }

     int mid=(left+right)/;

     node[x].mid=mid;

     build(left,mid,*x);

     build(mid+,right,*x+);

 }

 void pushdown(int x){

     if(node[x].lazy)

     {

         node[*x].lazy+=node[x].lazy;

         node[*x+].lazy+=node[x].lazy;

         node[x*].sum+=node[x].lazy;

         node[*x+].sum+=node[x].lazy;

         node[x].lazy=;

     }

 }

 void add(int left,int right,int x){

     if(node[x].left==left&&node[x].right==right)

     {

         node[x].sum++;

         node[x].lazy++;

         return;

     }

     pushdown(x);

     int mid=node[x].mid;

     if(right<=mid)

     {

         add(left,right,*x);

     }

     else if(mid<left)

     {

         add(left,right,*x+);

     }

     else

     {

         add(left,mid,*x);

         add(mid+,right,*x+);

     }

     node[x].sum=node[x*].sum+node[*x+].sum;

 }

 int get(int left,int right,int x)

 {

     if(node[x].left==node[x].right)

     {

         return node[x].sum;

     }

     pushdown(x);

     int mid=node[x].mid;

     if(left<=mid)

         return get(left,right,*x);

     else

         return get(left,right,*x+);

 }

 void change(int x,int y){

     int fx=f2[x],fy=f2[y];

     while(fx!=fy)

     {

         if(deep[fx]<deep[fy])

         {

             swap(fx,fy);

             swap(x,y);

         }

         add(dfn[fx],dfn[x],);

         x=fa[fx];

         fx=f2[x];

     }

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

     if(dfn[x]<=dfn[y])

         add(dfn[x],dfn[y],);

 }

 int main(){

     scanf("%d",&n);

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

         scanf("%d",&b[i]);

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

     {

         int x,y;

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

         build(x,y);

         build(y,x);

     }

     dfs(,);

     dfs2(,);

     build(,n,);

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

     {

         change(b[i-],b[i]);

     }

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

     {

         //cout<<endl;

         int x=get(dfn[i],dfn[i],);

         if(i!=b[])

             x--;

         printf("%d\n",x);

     }

     //while(1);

     return ;

 }

巴特西

树链剖分 [JLOI2014]松鼠的新家

[JLOI2014]松鼠的新家

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章