树链剖分 P2950树的统计(比模板还简单。。)
hicc0305
2018-05-20 20:36:29
哈哈哈哈哈哈哈,蒟蒻居然过了树剖,哈哈哈哈哈啊哈,嗝~
那么请开始我的树剖
------------
首先上定义:
定义siz(x)为以x为根的子树的结点个数。
令v为u的儿子结点中siz()值最大的结点:
重结点:子树结点数目最多的结点
轻节点:父亲节点中除了重结点以外的结点
重边:父亲结点和重结点连成的边,即边(u,v)
轻边:重边之外的边
重链:由多条重边连接而成的路径
轻链:由多条轻边连接而成的路径
一个非叶节点有且仅有一个重儿子
![](https://cdn.luogu.com.cn/upload/pic/19692.png)
加粗的链就是重链,注意4,7,8这三个点也是重链
------------
那么再上一堆数组:
siz[i]以i为根结点的子树中结点的数目
hson[i]结点i的重儿子的编号
dep[i]结点i的深度,根的深度为1
top[i]结点i所在的重链的链首结点编号
fa[i]结点i的父结点编号
tid[i]结点i剖分以后的新编号(dfs2序号)
rnk[i]结点i在树中的原位置:i为新编号,rnk[i]为原编号
------------
那么怎么求这些数组呢?
DFS1找重边 顺便求出siz[i],dep[i],fa[i],hson[i]
DFS2将重边连成重链 顺便求出top[i],tid[i],说的dfs2序号就是dfs序啦
![](https://cdn.luogu.com.cn/upload/pic/19693.png)
橙色的是原序号,绿色的是dfs序,注意,我们先走重儿子,连成重链,让一个重链中的数dfs全部连在一起,这样就为我们后面的线段树维护做了铺垫
![](https://cdn.luogu.com.cn/upload/pic/19694.png)
这样清楚一点
------------
现在是线段树维护部分
我们已经把树处理成了线性,那么我们就可以用线段树维护了
如果要求i~j的最大值,如果i和j在同一个重链中,我们就直接输出max(tid[i]~tid[j]),而如果不在同一个重链中,我们就让深度大的那一个爬树,爬到它的top,求出其中的最大值,直到两个数在同一重链中,我们再求一下取个max就可以输出了
那为什么不可以直接线段树呢?当然是因为不同重链并不一定不连续
至于修改的话,正常线段树修改就行了
------------
那么,代码时间
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0;
int a[300100],f[300100];
int head[300100],nxt[300100],to[300100];
int siz[300100],d[300100],hs[300100];
int top[300100],ran[300100],tid[300100];
int sum[300100],ma[300100];
void addedge(int x,int y,int cn)
{
nxt[cn]=head[x];
head[x]=cn;
to[cn]=y;
}
void dfs1(int u,int fa)
{
f[u]=fa,siz[u]=1;//求出fa,size,dep,hson
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
d[v]=d[u]+1;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hs[u]]) hs[u]=v;
}
}
void dfs2(int u,int h)
{
top[u]=h,tid[u]=++cnt,ran[cnt]=u;//求出top,tid,rank
if(!hs[u]) return;//重边走到头return
dfs2(hs[u],h);//先走重边
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(v==f[u] || v==hs[u]) continue;
dfs2(v,v);
}
}
void build(int l,int r,int x)//建树
{
if(l==r)
{
sum[x]=ma[x]=a[ran[l]];
return;
}
int mid=(l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
sum[x]=sum[x*2]+sum[x*2+1];
ma[x]=max(ma[x*2],ma[x*2+1]);
}
void Change(int l,int r,int x,int u,int v)//线段树修改
{
if(l==r)
{
ma[x]=sum[x]=v;
return;
}
int mid=(l+r)/2;
if(u<=mid) Change(l,mid,x*2,u,v);
else Change(mid+1,r,x*2+1,u,v);
sum[x]=sum[x*2]+sum[x*2+1];
ma[x]=max(ma[x*2],ma[x*2+1]);
}
int Clacm(int l,int r,int x,int L,int R)
{
if(L<=l && R>=r) return ma[x];
int mid=(l+r)/2;
if(R<=mid) return Clacm(l,mid,x*2,L,R);
else if(L>mid) return Clacm(mid+1,r,x*2+1,L,R);
else return max(Clacm(l,mid,x*2,L,R),Clacm(mid+1,r,x*2+1,L,R));
}
int Querym(int l,int r,int x,int u,int v)//max查询
{
int ans=-1000000000;//注意权值有负数,赋个负无穷
while(top[u]!=top[v])//不在同一重链中,爬树
{
if(d[top[u]]<d[top[v]]) swap(u,v);
ans=max(ans,Clacm(1,n,1,tid[top[u]],tid[u]));//深度大的那个爬到top,同时取u~top[u]的最大值max一下
u=f[top[u]];
}
if(d[u]<d[v]) swap(u,v);
ans=max(ans,Clacm(1,n,1,tid[v],tid[u]));//同一重链直接线段树求max
return ans;
}
int Clacs(int l,int r,int x,int L,int R)
{
if(L<=l && R>=r) return sum[x];
int mid=(l+r)/2;
if(R<=mid) return Clacs(l,mid,x*2,L,R);
else if(L>mid) return Clacs(mid+1,r,x*2+1,L,R);
else return Clacs(l,mid,x*2,L,R)+Clacs(mid+1,r,x*2+1,L,R);
}
int Querys(int l,int r,int x,int u,int v)//sum同理
{
int ans=0;
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]]) swap(u,v);
ans+=Clacs(1,n,1,tid[top[u]],tid[u]);
u=f[top[u]];
}
if(d[u]<d[v]) swap(u,v);
ans+=Clacs(1,n,1,tid[v],tid[u]);
return ans;
}
int main()
{
memset(hs,0,sizeof(hs));
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y,i*2-1);
addedge(y,x,i*2);
}
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
d[1]=1,dfs1(1,1),dfs2(1,1);
build(1,n,1);
char tmp[10];
int m,x,y;
scanf("%d",&m);
while(m--)
{
scanf("%s%d%d",tmp,&x,&y);
if(tmp[0]=='C') Change(1,n,1,tid[x],y);
else if(tmp[1]=='M') printf("%d\n",Querym(1,n,1,x,y));
else printf("%d\n",Querys(1,n,1,x,y));
}
return 0;
}
```