[bzoj1036]树的统计

发表于 2017-03-25   |   分类于 bzoj , 线段树  |  访问: 67 次

2016/7/26

一题裸题

树链剖分一下

再加个线段树

我加的那个线段树是zkw型的

比较容易调试

代码也比较轻量

有个问题就是得用两个变量来区分新编号大小

毕竟我们在zkw中把编号小的放在了前面

o和p两个变量就是用来区分这个大小的

第一次写树链剖分

感觉良好

 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int _maxn=30010; 
int siz[_maxn],fa[_maxn],top[_maxn],son[_maxn],tid[_maxn],a[_maxn],dep[_maxn];
int n,m,k,head[_maxn],newid,M;
struct e1{
    int maxn,sum;
}tree[_maxn<<2];
struct e{
    int to,Next;
}edge[_maxn<<1];
void add(int x,int y){
    ++k;edge[k].Next=head[x];edge[k].to=y;head[x]=k;
    ++k;edge[k].Next=head[y];edge[k].to=x;head[y]=k;
}
void dfs1(int x){
    int v;
    son[x]=-1;
    siz[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].Next){
        v=edge[i].to;
        if(v==fa[x])
            continue;
        dep[v]=dep[x]+1;
        fa[v]=x;
        dfs1(v);
        siz[x]+=siz[v];
        if(son[x]==-1 || siz[v]>siz[son[x]])
            son[x]=v;
    }
}
void dfs2(int u,int tp){
    int v;
    top[u]=tp;
    tid[u]=++newid;
    if(son[u]==-1)
        return;
    dfs2(son[u],tp);
    for(int i=head[u];i!=-1;i=edge[i].Next){
        v=edge[i].to;
        if(v==fa[u] || v==son[u])
            continue;
        dfs2(v,v);
    }
}
void push(int pos,int nu){
    pos+=M;
    tree[pos].maxn=tree[pos].sum=nu;
    pos>>=1;
    while(pos){
        tree[pos].maxn=max(tree[pos<<1].maxn,tree[(pos<<1)+1].maxn);
        tree[pos].sum=tree[pos<<1].sum+tree[(pos<<1)+1].sum;
        pos>>=1;
    }
}
int findmax(int y1,int y2){
    y1=y1+M-1;
    y2=y2+M+1;
    int ans=-50000;
    while(y1^y2^1){
        if(~y1&1)	ans=max(tree[y1+1].maxn,ans);
        if(y2&1)	ans=max(tree[y2-1].maxn,ans);
        y1>>=1;y2>>=1;
    }
    return ans;
}
//询问从u到v的最大值 
void querymax(int u,int v){
    int ans=-50000,o,p;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        o=tid[u];
        p=tid[top[u]];
        if(o>p)
            swap(o,p);
        ans=max(ans,findmax(o,p));
        u=fa[top[u]];
    }
    o=tid[u];
    p=tid[v];
    if(o>p)
        swap(o,p);
    ans=max(ans,findmax(o,p));
    printf("%d\n",ans);
}
long long findsum(int y1,int y2){
    long long ans=0;
    y1=y1+M-1;
    y2=y2+M+1;
    while(y1^y2^1){
        if(~y1&1)	ans+=tree[y1+1].sum;
        if(y2&1)	ans+=tree[y2-1].sum; 
        y1>>=1;y2>>=1;
    }
    return ans;
}
//询问从u到v的总和 
void querysum(int u,int v){
    long long ans=0;
    int o,p;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        o=tid[u];
        p=tid[top[u]];
        if(o>p)		swap(o,p);
        ans+=findsum(o,p);
        u=fa[top[u]];
    }
    o=tid[u];
    p=tid[v];
    if(o>p)
        swap(o,p);
    ans+=findsum(o,p);
    printf("%lld\n",ans);
}
int main(){
    memset(head,-1,sizeof(head));
    char ch[10]; 
    int x,y;
    //加边 
    scanf("%d",&n);
    for(int i=1;i<n;i++){
     	scanf("%d%d",&x,&y);
     	add(x,y);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    //树链剖分 
    fa[1]=dep[1]=1;
    dfs1(1);dfs2(1,1);
    
    //建树 
    M=1<<((int)log2(newid+1)+1);
    for(int i=1;i<=n;i++)
        push(tid[i],a[i]);
    
    //询问操作 
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",ch);
        scanf("%d%d",&x,&y);
        if(ch[0]=='C')		push(tid[x],y);
        else if(ch[1]=='M')	querymax(x,y);
        else				querysum(x,y);
    }
    return 0;
}

 

长久后的某一天 2017/3/25 突然想填坑

写点大家都看得懂的树剖

【深夜不画图

要图的请出门左转看别人博客的图

效果应该一样】

我们先来看看题目的要求

I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

是不是感觉似曾相识,有点像线段树 单点修改 以及 区间求最大值  区间求和

事实上是这样的,只不过在树上我们不好操作,于是有些人就想啊

咱们能不能把树以某种特殊的形式展开或者映射成一个序列,这样不就可以变成线段树了

于是树剖诞生

接下来清楚几个概念

树剖就是树链剖分,简言之,剖分一棵树,使树映射成一维的序列,即开个a[]数组就可以存下来的那种

然后是几个概念

重儿子,轻儿子:重儿子就是某个节点的子树中最大的那棵的节点,比如a有b,c两棵子树,b子树有4个节点,c子树有5个节点,那么c节点就是a节点的重儿子。除去重儿子剩下的都是轻儿子。

重边,轻边:顾名思义,重边就是连向重儿子的边,轻边不用解释了吧。

重链:由重边练成的一条链【可以模拟得到重边连在一起必定是一条链】

有了这些概念,我们就可以知道一棵树可以按照对每个点轻重划分形成多条不相交的重链

为了达到剖分后还能使用的效果,我们必须保留里面的一些信息

dep[i]:节点i的深度【树顶深度为1】

siz[i]:节点i的子树大小【包括i节点】

son[i]:节点i的重儿子

top[i]:i节点所在的重链的最顶上的节点

fa[i]:i节点的父亲节点

tid[i]:映射到一维数组后的下标【待会讲】

 

大致步骤

事实上我们所做的就是把树剖成一条条重链分离开来,再把这些重链首尾相接变成一维序列

1.用一遍dfs1()来完成对dep[i],siz[i],son[i],fa[i]的计算

2.用一遍dfs2()来完成映射和串链,即计算出top[i],tid[i]

3.把映射好后的一维数组拿来做线段树

4.线段树查询的时候是一点点查的,查后再并到fa[top[i]](这个是重要的思想,待会详讲)

下面来解析代码

首先是初始化fa[1]和dep[1] (因为1是顶点)

//树链剖分 
	fa[1]=dep[1]=1;
	dfs1(1);dfs2(1,1);

然后是dfs1()

我用的是边表,可根据个人爱好改编

x为当前节点,v为x的子节点

如果x还没有重儿子,或者已经有了重儿子son[x]但v的子树siz[v]大于son[x]的子树siz[son[x]]

根据定义,我们是需要把son[x]换成v的,其余没什么好讲的

void dfs1(int x){
	int v;
	son[x]=-1;
	siz[x]=1;
	for(int i=head[x];i!=-1;i=edge[i].Next){
		v=edge[i].to;
		if(v==fa[x])
			continue;
		dep[v]=dep[x]+1;
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
		if(son[x]==-1 || siz[v]>siz[son[x]])
			son[x]=v;
	}
}

接着dfs2()

tp是u的top,即top[u]=tp,也就是说只要和u同一条重链的top[]都是top[u]

而和u同条重链的必定是u的重儿子

所以就可以先把重儿子的都走完,把它们的top[]都弄成top[u]

直到son[u]=-1,也就是说u已经没有重儿子了,此时返回开始走轻边

假设u的轻边指向v,那么v必定是v所在的那条重链的top

所以可以继续dfs2(v,v)

得出规律:

1.重儿子的top值和自己的top值一样

2.轻儿子的top值就是轻儿子自己

而tid就是新编号,毕竟要把他们都拉到某个一维的数组里,它们在新数组里总得有个新编号

模拟一下就会发现,编好编号后,更像是把树剖分后,把重链首尾相接组成新一维数组

void dfs2(int u,int tp){
	int v;
	top[u]=tp;
	tid[u]=++newid;
	if(son[u]==-1)
		return;
	dfs2(son[u],tp);
	for(int i=head[u];i!=-1;i=edge[i].Next){
		v=edge[i].to;
		if(v==fa[u] || v==son[u])
			continue;
		dfs2(v,v);
	}
}

然后我建了棵zkw线段树

如果你不会写zkw线段树,看不懂我的代码,那么有两个办法

1.学习一下zkw线段树,受益无穷

2.学习一下原理,把它改成你自己的风格

原理:因为我们已经把树剖分连成了一个一维数组,故我们以这个一维数组建立线段树即可

新编号为tid[i],所对应的权值是a[i],所以朴素线段树应该是push(pos=1 , l=1 , r=n , x=tid[i] , key=a[i])

pos为[l,r]区间的编号,x为要插入的位置,key为插入的值

由于我们需要维护最大值和区间和,所以我用了结构体【当然开个二维的tree也是可以的】

//建树 
M=1<<((int)log2(newid+1)+1);
for(int i=1;i<=n;i++)
	push(tid[i],a[i]);

//function push
void push(int pos,int nu){
	pos+=M;
	tree[pos].maxn=tree[pos].sum=nu;
	pos>>=1;
	while(pos){
		tree[pos].maxn=max(tree[pos<<1].maxn,tree[(pos<<1)+1].maxn);
		tree[pos].sum=tree[pos<<1].sum+tree[(pos<<1)+1].sum;
		pos>>=1;
	}
}

自此,剖分+建树已经完成,接下来就是

修改操作

可以看到push函数即可单点修改权值,要将x的权值改为y就是把那个一直提到的假想中的一维数组下标为tid[x]的权值改成y,所以push操作一下就可以了,这里应该不难理解。

//询问操作 
scanf("%d",&m);
for(int i=1;i<=m;i++){
	scanf("%s",ch);
	scanf("%d%d",&x,&y);
	if(ch[0]=='C')		push(tid[x],y);
	else if(ch[1]=='M')	querymax(x,y);
	else			querysum(x,y);
}

查询最值就没那么好处理了

首先清楚它的工作原理,设查询的两个点为u,v

1.假如u,v在同一条重链上,因为它们在线段树上中间的节点就是他们在原树中的中间节点,所以我们直接查询线段树这个区间最大值是不是就行了【如果你前面有画出重链剖完连接在一起的图,不难发现这些简单的规律,如果没画,建议补画】

2.但是如果不在同一条重链上呢,这就是精妙的地方了。首先保持原树节点u的顶点深度大于v的顶点深度,如果不是,那么交换u,v,使dep[top[u]]>dep[top[v]];接着我们查一下u到u所在重链的顶点top[u]的最大值,因为u和top[u]在同一条重链上,所以查询就变成1的情况;查完这段还没完,我们需要把u变成fa[top[u]],这是因为u所在的这条重链已经查完了,不需要继续查找,所以把u变成fa[top[u]]就可以使u离开这条重链,然后重复做2直到u和v到达同一条重链上,此时情况变为1,完美的解决了问题。

findmax()函数就是简单的一个线段树查询最值罢了,可以自己改写成自己的风格

//询问从u到v的最大值 
void querymax(int u,int v){
	int ans=-50000,o,p;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])
			swap(u,v);
		o=tid[u];
		p=tid[top[u]];
		if(o>p)
			swap(o,p);
		ans=max(ans,findmax(o,p));
		u=fa[top[u]];
	}
	o=tid[u];
	p=tid[v];
	if(o>p)
		swap(o,p);
	ans=max(ans,findmax(o,p));
	printf("%d\n",ans);
}
int findmax(int y1,int y2){
    y1=y1+M-1; y2=y2+M+1; 
    int ans=-50000; 
    while(y1^y2^1){ 
        if(~y1&1) ans=max(tree[y1+1].maxn,ans); 
        if(y2&1) ans=max(tree[y2-1].maxn,ans); 
        y1>>=1;y2>>=1; 
    } 
    return ans; 
}

 

如果你理解了区间查询最大值的精妙

那么区间查询和对于你肯定不是什么难事

代码一并给出参考

long long findsum(int y1,int y2){
	long long ans=0;
	y1=y1+M-1;
	y2=y2+M+1;
	while(y1^y2^1){
		if(~y1&1)	ans+=tree[y1+1].sum;
		if(y2&1)	ans+=tree[y2-1].sum; 
		y1>>=1;y2>>=1;
	}
	return ans;
}
//询问从u到v的总和 
void querysum(int u,int v){
	long long ans=0;
	int o,p;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])
			swap(u,v);
		o=tid[u];
		p=tid[top[u]];
		if(o>p)		swap(o,p);
		ans+=findsum(o,p);
		u=fa[top[u]];
	}
	o=tid[u];
	p=tid[v];
	if(o>p)
		swap(o,p);
	ans+=findsum(o,p);
	printf("%lld\n",ans);
}

感谢听我扯淡

如果支持的人多以后还陆续更新别的算法

哪里不妥,评论区提出

如有雷同,我抄袭你的

转载的话标下出处吧

再次感谢阅读

发表新评论

© 2017 Powered by Typecho & Theme Quark