「BZOJ1036」[ZJOI2008] 树的统计Count

2014年4月6日39,51427

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身

Input

输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

题解

2014.4.6 树链剖分。。。

参照了蒋一瑶神犇模板

http://wenku.baidu.com/link?url=SGLjpJtYbJ0HxDYlU_GMXE1qCFS0gbmpDGWPxI7mQuNAsJP0y872mNKwpZ8P054g5XMhFGZbMUjZvN5hcnxFFUEfGBj6-tnkpnJvnVSlqGS

树链剖分就是把树拆成一系列链，然后用数据结构对链进行维护。

通常的剖分方法是轻重链剖分，所谓轻重链就是对于节点u的所有子结点v，size[v]最大的v与u的边是重边，其它边是轻边，其中size[v]是以v为根的子树的节点个数，全部由重边组成的路径是重路径，根据论文上的证明，任意一点到根的路径上存在不超过logn条轻边和logn条重路径。

这样我们考虑用数据结构来维护重路径上的查询，轻边直接查询。

通常用来维护的数据结构是线段树，splay较少见。

具体步骤

预处理

第一遍dfs求出树每个结点的深度deep[x]，其为根的子树大小size[x]

以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先

第二遍dfs

根节点为起点，向下拓展构建重链

选择最大的一个子树的根继承当前重链

其余节点，都以该节点为起点向下重新拉一条重链

给每个结点分配一个位置编号，每条重链就相当于一段区间，用数据结构去维护。

把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可

修改操作

1、单独修改一个点的权值

根据其编号直接在数据结构中修改就行了。

2、修改点u和点v的路径上的权值

（1）若u和v在同一条重链上

直接用数据结构修改pos[u]至pos[v]间的值。

（2）若u和v不在同一条重链上

一边进行修改，一边将u和v往同一条重链上靠，然后就变成了情况（1）。

查询操作

查询操作的分析过程同修改操作

题目不同，选用不同的数据结构来维护值，通常有线段树和splay

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define inf 0x7fffffff
#define N 30005 
#define M 60005
using namespace std;
int n,q,cnt,sz;
int v[N],dep[N],size[N],head[N],fa[N];
int pos[N],bl[N];
struct data{int to,next;}e[M];
struct seg{int l,r,mx,sum;}t[100005];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void ini()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
		int x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
	}
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
}
void dfs1(int x)
{
    size[x]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x])continue;
        dep[e[i].to]=dep[x]+1;
        fa[e[i].to]=x;
        dfs1(e[i].to);
        size[x]+=size[e[i].to];
    }
}
void dfs2(int x,int chain)
{
    int k=0;sz++;
    pos[x]=sz;//分配x结点在线段树中的编号
	bl[x]=chain;
    for(int i=head[x];i;i=e[i].next)
        if(dep[e[i].to]>dep[x]&&size[e[i].to]>size[k])
            k=e[i].to;//选择子树最大的儿子继承重链
    if(k==0)return;
    dfs2(k,chain);
    for(int i=head[x];i;i=e[i].next)
        if(dep[e[i].to]>dep[x]&&k!=e[i].to)
            dfs2(e[i].to,e[i].to);//其余儿子新开重链
}
void build(int k,int l,int r)//建线段树
{
    t[k].l=l;t[k].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void change(int k,int x,int y)//线段树单点修改
{
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==r){t[k].sum=t[k].mx=y;return;}
    if(x<=mid)change(k<<1,x,y);
    else change(k<<1|1,x,y);
    t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
    t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
int querysum(int k,int x,int y)//线段树区间求和
{
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==x&&y==r)return t[k].sum;
    if(y<=mid)return querysum(k<<1,x,y);
    else if(x>mid)return querysum(k<<1|1,x,y);
    else {return querysum(k<<1,x,mid)+querysum(k<<1|1,mid+1,y);}
}
int querymx(int k,int x,int y)//线段树区间求最大值
{
	
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==x&&y==r)return t[k].mx;
    if(y<=mid)return querymx(k<<1,x,y);
    else if(x>mid)return querymx(k<<1|1,x,y);
    else {return max(querymx(k<<1,x,mid),querymx(k<<1|1,mid+1,y));}
}
int solvesum(int x,int y)
{
	int sum=0;
    while(bl[x]!=bl[y])
    {
		if(dep[bl[x]]<dep[bl[y]])swap(x,y);
		sum+=querysum(1,pos[bl[x]],pos[x]);
		x=fa[bl[x]];
	}
	if(pos[x]>pos[y])swap(x,y);
	sum+=querysum(1,pos[x],pos[y]);
    return sum;
}
int solvemx(int x,int y)
{
	int mx=-inf;
    while(bl[x]!=bl[y])
    {
		if(dep[bl[x]]<dep[bl[y]])swap(x,y);
		mx=max(mx,querymx(1,pos[bl[x]],pos[x]));
		x=fa[bl[x]];
	}
	if(pos[x]>pos[y])swap(x,y);
	mx=max(mx,querymx(1,pos[x],pos[y]));
    return mx;
}
void solve()
{
    build(1,1,n);
    for(int i=1;i<=n;i++)
        change(1,pos[i],v[i]);
    scanf("%d",&q);
	char ch[10];
    for(int i=1;i<=q;i++) 
    {
        int x,y;scanf("%s%d%d",ch,&x,&y);
        if(ch[0]=='C'){v[x]=y;change(1,pos[x],y);}
        else
        {
            if(ch[1]=='M')
               printf("%d\n",solvemx(x,y));
            else
                printf("%d\n",solvesum(x,y));
        }
    }
}
int main()
{
    ini();
    dfs1(1);
    dfs2(1,1);
	solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#define inf 0x7fffffff

#define N 30005

#define M 60005

using namespace std;

int n,q,cnt,sz;

int v[N],dep[N],size[N],head[N],fa[N];

int pos[N],bl[N];

struct data{int to,next;}e[M];

struct seg{int l,r,mx,sum;}t[100005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;

}

void ini()

{

scanf("%d",&n);

for(int i=1;i<n;i++)

{

int x,y;

scanf("%d%d",&x,&y);

insert(x,y);

}

for(int i=1;i<=n;i++)scanf("%d",&v[i]);

}

void dfs1(int x)

{

size[x]=1;

for(int i=head[x];i;i=e[i].next)

{

if(e[i].to==fa[x])continue;

dep[e[i].to]=dep[x]+1;

fa[e[i].to]=x;

dfs1(e[i].to);

size[x]+=size[e[i].to];

}

void dfs2(int x,int chain)

{

int k=0;sz++;

pos[x]=sz;//分配x结点在线段树中的编号

bl[x]=chain;

for(int i=head[x];i;i=e[i].next)

if(dep[e[i].to]>dep[x]&&size[e[i].to]>size[k])

k=e[i].to;//选择子树最大的儿子继承重链

if(k==0)return;

dfs2(k,chain);

for(int i=head[x];i;i=e[i].next)

if(dep[e[i].to]>dep[x]&&k!=e[i].to)

dfs2(e[i].to,e[i].to);//其余儿子新开重链

}

void build(int k,int l,int r)//建线段树

{

t[k].l=l;t[k].r=r;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

void change(int k,int x,int y)//线段树单点修改

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==r){t[k].sum=t[k].mx=y;return;}

if(x<=mid)change(k<<1,x,y);

else change(k<<1|1,x,y);

t[k].sum=t[k<<1].sum+t[k<<1|1].sum;

t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);

}

int querysum(int k,int x,int y)//线段树区间求和

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==x&&y==r)return t[k].sum;

if(y<=mid)return querysum(k<<1,x,y);

else if(x>mid)return querysum(k<<1|1,x,y);

else {return querysum(k<<1,x,mid)+querysum(k<<1|1,mid+1,y);}

}

int querymx(int k,int x,int y)//线段树区间求最大值

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==x&&y==r)return t[k].mx;

if(y<=mid)return querymx(k<<1,x,y);

else if(x>mid)return querymx(k<<1|1,x,y);

else {return max(querymx(k<<1,x,mid),querymx(k<<1|1,mid+1,y));}

}

int solvesum(int x,int y)

{

int sum=0;

while(bl[x]!=bl[y])

{

if(dep[bl[x]]<dep[bl[y]])swap(x,y);

sum+=querysum(1,pos[bl[x]],pos[x]);

x=fa[bl[x]];

}

if(pos[x]>pos[y])swap(x,y);

sum+=querysum(1,pos[x],pos[y]);

return sum;

}

int solvemx(int x,int y)

{

int mx=-inf;

while(bl[x]!=bl[y])

{

if(dep[bl[x]]<dep[bl[y]])swap(x,y);

mx=max(mx,querymx(1,pos[bl[x]],pos[x]));

x=fa[bl[x]];

}

if(pos[x]>pos[y])swap(x,y);

mx=max(mx,querymx(1,pos[x],pos[y]));

return mx;

}

void solve()

{

build(1,1,n);

for(int i=1;i<=n;i++)

change(1,pos[i],v[i]);

scanf("%d",&q);

char ch[10];

for(int i=1;i<=q;i++)

{

int x,y;scanf("%s%d%d",ch,&x,&y);

if(ch[0]=='C'){v[x]=y;change(1,pos[x],y);}

else

{

if(ch[1]=='M')

printf("%d\n",solvemx(x,y));

else

printf("%d\n",solvesum(x,y));

}

int main()

{

ini();

dfs1(1);

dfs2(1,1);

solve();

return 0;

}

2014.8.7 *1

2015.2.5 *1

link cut tree 也很短啊

而且十分优美

动态树可以维护一个动态的森林，支持树的合并（两棵合并成一棵），分离（把某个点和它父亲点分开），动态LCA，树上的点权和边权维护、查询（单点或者树上的一条路径），换根。

《动态树的基本操作介绍以及相关证明》

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
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;
}
int n,m,top;
int fa[30005],c[30005][2],u[30005],v[30005],q[30005];
ll w[30005],sum[30005],mx[30005];
bool rev[30005];
bool isroot(int x)
{
	return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	sum[x]=sum[l]+sum[r]+w[x];
	mx[x]=max(w[x],max(mx[l],mx[r]));
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(rev[x])
	{
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l,r;
	l=(c[y][1]==x);r=l^1;
	if(!isroot(y))c[z][c[z][1]==y]=x;
	fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x)
{
	q[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])
		q[++top]=fa[i];
	while(top)pushdown(q[top--]);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	for(int t=0;x;t=x,x=fa[x])
		splay(x),c[x][1]=t,update(x);
}
void makeroot(int x)
{
	access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
	makeroot(x);fa[x]=y;
}
void split(int x,int y)
{
	makeroot(x);access(y);splay(y);
}
int main()
{
	n=read();mx[0]=-inf;
	for(int i=1;i<n;i++)
		u[i]=read(),v[i]=read();
	for(int i=1;i<=n;i++)
	{
		w[i]=read();
		sum[i]=mx[i]=w[i];
	}
	for(int i=1;i<n;i++)
		link(u[i],v[i]);
	m=read();
	char ch[10];
	int u,v;
	while(m--)
	{
		scanf("%s",ch);
		u=read();v=read();
		if(ch[1]=='H')
		{
			splay(u);
			w[u]=v;
			update(u);
		}
		if(ch[1]=='M')
			split(u,v),printf("%lld\n",mx[v]);
		if(ch[1]=='S')
			split(u,v),printf("%lld\n",sum[v]);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<complex>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

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;

}

int n,m,top;

int fa[30005],c[30005][2],u[30005],v[30005],q[30005];

ll w[30005],sum[30005],mx[30005];

bool rev[30005];

bool isroot(int x)

{

return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;

}

void update(int x)

{

int l=c[x][0],r=c[x][1];

sum[x]=sum[l]+sum[r]+w[x];

mx[x]=max(w[x],max(mx[l],mx[r]));

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

if(rev[x])

{

rev[x]^=1;rev[l]^=1;rev[r]^=1;

swap(c[x][0],c[x][1]);

}

void rotate(int x)

{

int y=fa[x],z=fa[y],l,r;

l=(c[y][1]==x);r=l^1;

if(!isroot(y))c[z][c[z][1]==y]=x;

fa[c[x][r]]=y;fa[y]=x;fa[x]=z;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x)

{

q[++top]=x;

for(int i=x;!isroot(i);i=fa[i])

q[++top]=fa[i];

while(top)pushdown(q[top--]);

while(!isroot(x))

{

int y=fa[x],z=fa[y];

if(!isroot(y))

{

if(c[y][0]==x^c[z][0]==y)rotate(x);

else rotate(y);

}

rotate(x);

}

void access(int x)

{

for(int t=0;x;t=x,x=fa[x])

splay(x),c[x][1]=t,update(x);

}

void makeroot(int x)

{

access(x);splay(x);rev[x]^=1;

}

void link(int x,int y)

{

makeroot(x);fa[x]=y;

}

void split(int x,int y)

{

makeroot(x);access(y);splay(y);

}

int main()

{

n=read();mx[0]=-inf;

for(int i=1;i<n;i++)

u[i]=read(),v[i]=read();

for(int i=1;i<=n;i++)

{

w[i]=read();

sum[i]=mx[i]=w[i];

}

for(int i=1;i<n;i++)

link(u[i],v[i]);

m=read();

char ch[10];

int u,v;

while(m--)

{

scanf("%s",ch);

u=read();v=read();

if(ch[1]=='H')

{

splay(u);

w[u]=v;

update(u);

}

if(ch[1]=='M')

split(u,v),printf("%lld\n",mx[v]);

if(ch[1]=='S')

split(u,v),printf("%lld\n",sum[v]);

}

return 0;

}

« NOIP2012借教室「BZOJ2243」[SDOI2011] 染色 »

iamgqr

活捉Menci大佬

某

学长第一个程序的t数组为啥开100000呢？开60000可以吗？。。。表示自己写了个开60000RE，开100000才过的

hzwer

线段树3倍以上比较稳妥

Menci

new 比较稳妥 23333

ZLY

黄学长，你第一个程序中这句话里的chain是什么意思void dfs2(int x,int chain)

hzwer

重链的链首标号

ZLY

谢谢黄学长

蒟蒻

可以用switch写成switch（ch）吗？

hzwer

没什么区别0。0

shiyukun

求解makeroot的作用啊不懂那个rev

hzwer

请手画练习2333

shiyukun

QAQ 就是一直觉得这样rev一下深度不就乱了吗果然我还是多看看比较好吗

hzwer

画一棵树，考虑换根的影响。。

MoonLight

请问一下我用lct写的时候，读进来一个个link会WA…换成神犇你那样dfs连边才过的…为何不能一个个link呢…

MoonLight

我的理解是无根树所以fa乱了就乱了吧…我理解错了么…

hzwer

QAQ 可以一个个link

Nfluqpz

学长教我树链剖分吧 T_T

hzwer

哪个神犇卖萌

Nfluqpz

orz

hzwer

副队你不知道我会查ip么

Nfluqpz

orz 您不会以为我这个ID是乱打的吧？

hzwer

漳州的ip

Nfluqpz

太过分了漳平既不是漳州也不属于漳州！！

hzwer

2333我这里显示是漳州，还有副队暴露了

Mektpoy

太逗了我不就是把名字稍微加了一点密么为什么还要用IP来查我。。

hzwer

卧槽刚发现。。这个在后台很容易看到的

hzwer.com _ Home | http://hzwer.com

「BZOJ1036」[ZJOI2008] 树的统计Count

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论