本文主要是介绍BZOJ 3631 [JLOI2014]松鼠的新家 树链剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
Input
第一行一个整数n，表示房间个数
第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
Output
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
Sample Input
5
1 4 5 3 2
1 2
2 4
2 3
4 5
1 4 5 3 2
1 2
2 4
2 3
4 5
Sample Output
1
2
1
2
1
2
1
2
1
HINT
2<= n <=300000
Source
原题链接
说实话原题链接这个东西，，有时候记得我才加一下。。QAQ
这题对样例的理解花了我一定时间，，但是发现看题目描述会更加好懂。
大意不说了！
首先这题我觉得可以LCA+树上差分搞出来的。
但是我还是选树链剖分吧。
这题比较简单，维护都不用线段树。。（区间修改，单点查询）
维护一个数组s，x~y都加1时，s[x]++，s[y+1]--就好了（很好的一个思想）
接着对s作前缀和处理就行。注意一下仍然是树上id的位置。
明天要去上学。。本来觉着10分钟可以秒了的。。
结果竟然！快读错了好久没发现！！
花了足足20分钟啊。。。。。
代码还是比较轻松的。。
其实跑起来速度还不错。（BZOJ上只有850+ms）
#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=300005;
int n,Ecnt,cnt;
int a[N],s[N];
struct Edge{int next,to;
}E[N<<1]; int head[N];
struct Tree{int pre,sz,son,top,tid,deep;
}tree[N];
void add(int u,int v){E[++Ecnt].next=head[u];E[Ecnt].to=v;head[u]=Ecnt;
}
void build(int x,int pre,int depth){tree[x].pre=pre;tree[x].sz=1;tree[x].son=0;tree[x].deep=depth;int maxx=0;for (int i=head[x];i;i=E[i].next){int j=E[i].to;if (j!=pre){build(j,x,depth+1);tree[x].sz+=tree[j].sz;if (maxx<tree[j].sz){maxx=tree[j].sz;tree[x].son=j;}}}
}
void getlink(int x,int ancestor){tree[x].top=ancestor;tree[x].tid=++cnt;if (tree[x].son) getlink(tree[x].son,ancestor);for (int i=head[x];i;i=E[i].next){int j=E[i].to;if (j!=tree[x].son && j!=tree[x].pre) getlink(j,j);}
}
void update(int x,int y){s[x]++; s[y+1]--;
}
void work(int u,int v){while (tree[u].top!=tree[v].top){if (tree[tree[u].top].deep<tree[tree[v].top].deep) swap(u,v);update(tree[tree[u].top].tid,tree[u].tid);u=tree[tree[u].top].pre;}if (tree[u].deep>tree[v].deep) swap(u,v);update(tree[u].tid,tree[v].tid);
}
int main(){n=read();for (int i=1;i<=n;i++) a[i]=read();int u,v; Ecnt=0;for (int i=1;i<n;i++){u=read(),v=read();add(u,v); add(v,u);}build(1,0,0);cnt=0; getlink(1,1);for (int i=1;i<n;i++)work(a[i],a[i+1]);s[0]=0;for (int i=1;i<=n;i++) s[i]+=s[i-1];s[tree[a[1]].tid]++;for(int i=1;i<=n;i++)printf("%d\n",s[tree[i].tid]-1);return 0;
}这篇关于BZOJ 3631 [JLOI2014]松鼠的新家 树链剖分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![[HDU 5029] Relief grain （树链剖分+线段树）](/front/images/it_default.gif)
