洛谷P3833

Description

树链剖分板子题

考查两种操作

A u v w 把 u 节点到 v 节点路径上所有节点权值加 w
Q u 求以 u 为根节点的子树权值之和

首先需要了解线段树和 dfs 序，我这里没有很好的链接，不熟悉的再自行百度吧

另外了解树链剖分的思想（重儿子等等），否则会出很多千奇百怪的错误

树链剖分的构成

DFS1 来处理每个点的深度，他的父节点以及他的重儿子

DFS2 来处理每条链的链顶，每个点的 dfs 序和他们的 pre（建树时用）

然后就是各种操作函数

这里就不止说这个题了，顺便说一下树链剖分的其他几种操作

线段树也有很多操作，一些题可能会同时考到

但线段树就不说了，回去翻板子题的教程吧

分享几个树剖典型题目 P2590 P3178 和 P4315

Solution

操作一区间加

树链剖分最常用操作之一

void change1(int x,int y,int val){

		while(top[x]!=top[y]){

		    if(depth[top[x]]<depth[top[y]]) swap(x,y);

			update(1,1,n,val,dfn[top[x]],dfn[x]);

			x=fa[top[x]];

		}

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

		update(1,1,n,val,dfn[x],dfn[y]);

	}

操作二区间求和

int qsum1(int x,int y){

		int ans=0;

		while(top[x]!=top[y]){

		    if(depth[top[x]]<depth[top[y]]) swap(x,y);

			ans+=query(1,1,n,dfn[top[x]],dfn[x]);

			x=fa[top[x]];

		}

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

		ans+=query(1,1,n,dfn[x],dfn[y]);

		return ans;

	}

操作三区间取最大值

int qmax(int x,int y){

		int ans=-101010101;

		while(top[x]!=top[y]){

		    if(depth[top[x]]<depth[top[y]]) swap(x,y);

			ans=max(ans,qmax(1,1,n,dfn[top[x]],dfn[x]));

			x=fa[top[x]];

		}

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

		ans=max(ans,qmax(1,1,n,dfn[x],dfn[y]));

		return ans;

	}

取最小值也是一样的

不过建树的时候注意处理最大值

操作四子树上加

在以某点为根节点的子树上加值

	void change2(int x,int val){update(1,dfn[x],dfn[x]+size[x]-1,val,1,n);}

看起来很简单对吧，其实只需要知道他的思想就好了

操作五子树取和

	int qsum2(int x){return query(1,dfn[x],dfn[x]+size[x]-1,1,n);}

这是我见的比较常用的几种操作

而且一些树链剖分的操作是不用专门来写函数的

就像上面的子树上操作一样

Code

再给下本题的代码，其实不是很必要了

没写注释，大家将就看吧

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<cmath>

#define maxn 10001000

#define INF 0x3f3f3f3f

#define int long long

#define lson x<<1

#define rson x<<1|1

using namespace std;

char s;

int n,q,cnt,tot,lazy[maxn],head[maxn],sum[maxn],a[maxn],size[maxn],dfn[maxn],depth[maxn],top[maxn],fa[maxn],pre[maxn],mmax[maxn],son[maxn];

struct edge{int fr,to,nxt;}e[maxn*2];

void addedge(int fr,int to){e[++tot].to=to;e[tot].nxt=head[fr];head[fr]=tot;}

int read(){

	int s=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0' &&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}

	return s*w;

}

namespace Seg{

	void pushup(int x){sum[x]=sum[lson]+sum[rson];}

	void pushdown(int x,int ln,int rn){

		if(lazy[x]){

		    lazy[lson]+=lazy[x];

			lazy[rson]+=lazy[x];

			sum[lson]+=lazy[x]*ln;

			sum[rson]+=lazy[x]*rn;

			lazy[x]=0;

		}

	}

	void build(int x,int l,int r){

		lazy[x]=0;

		if(l==r){sum[x]=0;return;}

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

		build(lson,l,mid);build(rson,mid+1,r);

		pushup(x);

	}

	void update(int x,int l,int r,int val,int L,int R){

		if(L<=l &&r<=R){sum[x]+=(r-l+1)*val;lazy[x]+=val;return;}

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

		pushdown(x,mid-l+1,r-mid);

		if(L<=mid) update(lson,l,mid,val,L,R);

		if(R>mid) update(rson,mid+1,r,val,L,R);

		pushup(x);

	}

	int query(int x,int l,int r,int L,int R){

		if(L<=l &&r<=R) return sum[x];

		int ans=0;

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

		pushdown(x,mid-l+1,r-mid);

        if(l>R||r<L) return 0;

		if(L<=mid) ans+=query(lson,l,mid,L,R);

		if(R>mid) ans+=query(rson,mid+1,r,L,R);

		return ans;

	}

}

namespace Cut{

	void dfs1(int x,int fat){

		size[x]=1;depth[x]=depth[fat]+1;fa[x]=fat;

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

			int to=e[i].to;

			if(to==fat) continue;

			dfs1(to,x);

			size[x]+=size[to];

			if(size[son[x]]<size[to]) son[x]=to;

		}

	}

	void dfs2(int x,int tp){

		top[x]=tp;dfn[x]=++cnt;pre[cnt]=x;

		if(son[x]) dfs2(son[x],tp);

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

			int to=e[i].to;

			if(to==son[x]||to==fa[x]) continue;

			dfs2(to,to);

		}

	}

	void change1(int x,int y,int val){

		while(top[x]!=top[y]){

		    if(depth[top[x]]<depth[top[y]]) swap(x,y);

			Seg::update(1,1,n,val,dfn[top[x]],dfn[x]);

			x=fa[top[x]];

		}

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

		Seg::update(1,1,n,val,dfn[x],dfn[y]);

	}

	int qsum1(int x,int y){

		int ans=0;

		while(top[x]!=top[y]){

		    if(depth[top[x]]<depth[top[y]]) swap(x,y);

			ans+=Seg::query(1,1,n,dfn[top[x]],dfn[x]);

			x=fa[top[x]];

		}

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

		ans+=Seg::query(1,1,n,dfn[x],dfn[y]);

		return ans;

	}

	void change2(int x,int val){Seg::update(1,1,n,val,dfn[x],dfn[x]+size[x]-1);}

	int qsum2(int x){return Seg::query(1,1,n,dfn[x],dfn[x]+size[x]-1);}

}

signed main(){

	n=read();

//	for(int i=1;i<=n;i++) a[i]=i-1;

	for(int i=1,fs,es;i<n;i++){fs=read()+1;es=read()+1;addedge(fs,es);addedge(es,fs);}

	Cut::dfs1(1,0);Cut::dfs2(1,1);Seg::build(1,1,n);

	q=read();

	for(int i=1,fs,es,ds;i<=q;i++){

	    cin>>s;

	    if(s =='A'){

	    	fs=read()+1;es=read()+1;ds=read();

			Cut::change1(fs,es,ds);

		}

		if(s =='Q'){

			fs=read()+1;

			printf("%lld\n",Cut::qsum2(fs));

		}

	}

	return 0;

}

ps：

本题每个点的初始权值是 0 ，序号是 1 到 n，

我看成了初始权值为 1 到 n ，然后就 D 了好久

另外注意编号从 0 开始，要在输入加边或者 dfs 建树的地方处理一下

希望对大家有帮助

巴特西

洛谷P3833

Description

树链剖分的构成

Solution

操作一区间加

操作二区间求和

操作三区间取最大值

操作四子树上加

操作五子树取和

Code

最新文章

热门文章

巴特西

洛谷P3833

Description

树链剖分的构成

Solution

操作一 区间加

操作二 区间求和

操作三 区间取最大值

操作四 子树上加

操作五 子树取和

Code

最新文章

热门文章

操作一区间加

操作二区间求和

操作三区间取最大值

操作四子树上加

操作五子树取和