树链剖分板子题
先说点别的
小熊维尼啊，嘿嘿嘿。
写题经历
悲惨命运：树剖调了2天，一直90分，死活不AC，调出了心病，快下课时改了一下数据范围，A了……。（刚开始数组开了800100，改1200100过了）
所以说啊，线段树必须要注意数据范围，要开4倍，不然会想傻X作者一样调出心病。（太可怕了，数据范围小了，不RE，竟然WA，评测机太可怕了QAQ）
吐槽，树链剖分题怎么都比【模板】树链剖分 简单
前置技能
1、线段树 2、树链剖分
如果你已经过了P3384 【模板】树链剖分这道题。那么这道题就是附赠的紫题哈。
思路
我们知道树链剖分支持以下操作：
1、在树中将u到v节点数值全部加一个值。
2、查询树中u到v节点的数值和
那么我们可以想到把小熊维尼去每一个房间抽象成一个一个点，那么我们要从u房间去到v房间，则要在u到v之间都放一个糖果，于是我们将松鼠它家u到v的糖果数都加1。
看到这里，想到树剖写法了吧，每一次将a[i]到a[i+1] (a数组是访问顺序)的节点加1，这个可以用树链剖分做。
查询只需要查每个点的权值就OK了。
当然还有些细节，在处理完一次修改后，终点要减1，不然会重复计算。
代码
//by:hyfhaha
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1200100; //特以此纪念本人数据范围开小卡90分卡两天
int a[maxn],tree[maxn],tag[maxn],n,m,mode,x,y,z,S,cnt;
int large[maxn],seg[maxn],father[maxn],vis[maxn],dep[maxn],son[maxn],rev[maxn],top[maxn];
int Next[maxn],head[maxn],from[maxn],to[maxn],id[maxn],tot;
//********************以下线段树********************
void pushdown(int node,int begin,int end){
if(tag[node]){
int m=(begin+end)/2;
tree[node*2]+=tag[node]*(m-begin+1);
tree[node*2+1]+=tag[node]*(end-m);
tag[node*2]+=tag[node];
tag[node*2+1]+=tag[node];
tag[node]=0;
}
}
int query(int node,int begin,int end,int x,int y){
if(x<=begin&&end<=y)
return tree[node];
else{
int m=(begin+end)/2,res=0;
pushdown(node,begin,end);
if(x<=m)
res+=query(node*2,begin,m,x,y);
if(y>m)
res+=query(node*2+1,m+1,end,x,y);
return res;
}
}
void update(int node,int begin,int end,int x,int y,int val){
if(x<=begin&&end<=y){
tree[node]+=val*(end-begin+1);
tag[node]+=val;
}
else{
int m=(begin+end)/2;
pushdown(node,begin,end);
if(x<=m){
update(node*2,begin,m,x,y,val);
}
if(y>m){
update(node*2+1,m+1,end,x,y,val);
}
tree[node]=tree[node*2]+tree[node*2+1];
}
}
//********************以上线段树********************
//********************以下树链剖分********************
void dfs1(int x,int f){
large[x]=1;father[x]=f;
dep[x]=dep[f]+1;
int maxy=0;
for(int i=head[x];i!=-1;i=Next[i]){
int u=to[i],big=0;
if(u==f)continue;
dfs1(u,x);
large[x]+=large[u];
if(large[u]>maxy){son[x]=u;maxy=large[u];}
}
}
void dfs2(int x,int f){
top[x]=f;id[x]=++tot;
if(!son[x]){
return;
}
dfs2(son[x],f);
for(int i=head[x];i!=-1;i=Next[i]){
int u=to[i];
if(u!=son[x]&&u!=father[x]){
dfs2(u,u);
}
}
}
void updatelong(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<=dep[top[y]]){
update(1,1,n,id[top[y]],id[y],z);
y=father[top[y]];
}else{
update(1,1,n,id[top[x]],id[x],z);
x=father[top[x]];
}
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],z);
}
//********************以上树链剖分********************
void add(int x,int y){ //建边
cnt++;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
//********************以下主程序********************
int main(){
scanf("%d",&n);S=1;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs1(S,0);dfs2(S,S);
for(int i=1;i<=n-1;i++){
updatelong(a[i],a[i+1],1);
updatelong(a[i+1],a[i+1],-1);//记得终点减1
}
for(int i=1;i<=n;i++)
printf("%d\n",query(1,1,n,id[i],id[i]));
}//光棍数字收场