4633 [Mz]树链剖分练习
时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master
题目描述 Description
给定一棵结点数为n的树，初始点权均为0，有依次q个操作，每次操作有三个参数a,b,c，当a=1时，表示给b号结点到c号结点路径上的所有点（包括b,c，下同）权值都增加1，当a=2时，表示询问b号结点到c号结点路径上的所有点权值之和。
输入描述 Input Description
第一行，一个正整数n。
接下来n-1行，每行一对正整数x,y，表示x号结点和y号结点之间有一条边。
第n+1行，一个正整数q。
最后q行，每行一组正整数a,b,c，表示操作的三个参数。b和c可能相等。
保证数据都是合法的。
输出描述 Output Description
若干行，每行一个非负整数表示答案。
样例输入 Sample Input
5
1 2
2 3
1 4
2 5
5
1 4 5
2 1 5
1 1 3
2 5 3
2 4 3
样例输出 Sample Output
3
4
6
数据范围及提示 Data Size & Hint
共有10个测试点，对于第i个测试点，当1<=i<=4时，n=q=10^i，当5<=i<=10时，n=q=10000*i。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 10000*10
struct Edge{ int to,next,value; }e[maxn*+];
struct Node{ int l,r,sum,lazy; }tre[maxn*];
int dep[maxn],pos[maxn],size[maxn],son[maxn],fa[maxn];
int top[maxn],head[maxn],tot=,n,visx;
void Add_Edge(int u,int v){
e[++tot].to=v;e[tot].next=head[u];
head[u]=tot;
}
void DFS_First(int now,int pre,int deepth){
fa[now]=pre;size[now]=;dep[now]=deepth;
for(int i=head[now];i;i=e[i].next){
int v=e[i].to;
if(v!=pre&&!dep[v]){
DFS_First(v,now,deepth+);
size[now]+=size[v];
if(!son[now]||size[son[now]]<size[v])
son[now]=v;
}
}
}
void DFS_Second(int now,int Top){
pos[now]=++visx;top[now]=Top;
if(son[now])DFS_Second(son[now],Top);
for(int i=head[now];i;i=e[i].next){
int v=e[i].to;
if(v!=son[now]&&v!=fa[now])DFS_Second(v,v);
}
}
void Build(int now,int l,int r){
tre[now].l=l;tre[now].r=r;
if(l==r)return;
int mid=(l+r)>>;
Build(now<<,l,mid);Build(now<<|,mid+,r);
}
void down(int now){
int k=tre[now].lazy;
tre[now<<].lazy+=k;tre[now<<|].lazy+=k;
tre[now].lazy=;
tre[now<<].sum+=k*(tre[now<<].r-tre[now<<].l+);
tre[now<<|].sum+=k*(tre[now<<|].r-tre[now<<|].l+);
}
int query(int now,int l,int r){
if(l<=tre[now].l&&tre[now].r<=r)return tre[now].sum;
if(tre[now].lazy)down(now);
int ans=,mid=(tre[now].l+tre[now].r)>>;
if(mid>=l)ans+=query(now<<,l,r);
if(mid<r)ans+=query(now<<|,l,r);
tre[now].sum=tre[now<<].sum+tre[now<<|].sum;
return ans;
}
int QuerySum(int u,int v){
int ans=;
while(top[u]!=top[v]){
if(dep[top[u]] < dep[top[v]])swap(u,v);
ans+=query(,pos[top[u]],pos[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
ans+=query(,pos[u],pos[v]);
return ans;
}
void UpDate(int now,int l,int r){
if(l<=tre[now].l&&tre[now].r<=r){
tre[now].lazy++;
tre[now].sum+=tre[now].r-tre[now].l+;
return ;
}
if(tre[now].lazy)down(now);
int mid=(tre[now].l+tre[now].r)/;
if(mid>=l)UpDate(now<<,l,r);
if(mid<r)UpDate(now<<|,l,r);
tre[now].sum=tre[now<<].sum+tre[now<<|].sum;
return ;
}
void Change(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
UpDate(,pos[top[u]],pos[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
UpDate(,pos[u],pos[v]);
}
int main(){
scanf("%d",&n);
int q,x,y,z;
for(int i=,u,v;i<n;i++){
scanf("%d%d",&u,&v);
Add_Edge(u,v);Add_Edge(v,u);
}
DFS_First(,,);
DFS_Second(,);
Build(,,n); scanf("%d",&q);
while(q--){
scanf("%d%d%d",&x,&y,&z);
if(x==)Change(y,z);
else printf("%d\n",QuerySum(y,z));
}
return ;
}
