树链剖分【洛谷P3833】 [SHOI2012]魔法树

P3833 [SHOI2012]魔法树

题目描述

Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u] < u。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即0个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：

Add u v d

表示将点u和v之间的路径上的所有节点的果子个数都加上d。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：

Query u

表示当前果树中，以点u为根的子树中，总共有多少个果子？

输入输出格式

输入格式：

第一行一个正整数N (1 ≤ N ≤ 100000)，表示果树的节点总数，节点以0,1,…,N − 1标号，0一定代表根节点。

接下来N − 1行，每行两个整数a,b (0 ≤ a < b < N)，表示a是b的父亲。

接下来是一个正整数Q(1 ≤ Q ≤ 100000)，表示共有Q次操作。

后面跟着Q行，每行是以下两种中的一种：

A u v d，表示将u到v的路径上的所有节点的果子数加上d；0 ≤ u,v <N,0 < d < 100000

Q u，表示询问以u为根的子树中的总果子数，注意是包括u本身的。

输出格式：

对于所有的Query操作，依次输出询问的答案，每行一个。答案可能会超过2^32 ，但不会超过10^15 。

省选考树剖裸题。。。

code：

#include <iostream>

#include <cstdio>

#define ls(o) o<<1

#define rs(o) o<<1|1

#define int long long

using namespace std;

const int wx=100017;

inline int read(){

	int sum=0,f=1;char ch=getchar();

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

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

	return sum*f;

}

int dfn[wx],tid[wx];

int dep[wx],f[wx],size[wx],son[wx];

int top[wx];

int head[wx],a[wx];

int n,m,num,tot;

char opt[17];

struct val_tree{

	int l,r,tag,sum;

	#define tag(o) t[o].tag

	#define sum(o) t[o].sum

}t[wx*4];

void up(int o){

	sum(o)=sum(ls(o))+sum(rs(o));

}

void down(int o){

	if(tag(o)){

		sum(ls(o))+=tag(o)*(t[ls(o)].r-t[ls(o)].l+1);

		sum(rs(o))+=tag(o)*(t[rs(o)].r-t[rs(o)].l+1);

		tag(ls(o))+=tag(o); tag(rs(o))+=tag(o);

		tag(o)=0;

	}

}

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

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

	if(l==r){sum(o)=a[tid[l]];return ;}

	int mid=t[o].l+t[o].r>>1;

	if(l<=mid)build(ls(o),l,mid);

	if(r>mid)build(rs(o),mid+1,r);

	up(o);

}

void update_t(int o,int l,int r,int k){

	if(l<=t[o].l&&t[o].r<=r){

		sum(o)+=k*(t[o].r-t[o].l+1);

		tag(o)+=k; return ;

	}

	down(o);

	int mid=t[o].l+t[o].r>>1;

	if(l<=mid)update_t(ls(o),l,r,k);

	if(r>mid)update_t(rs(o),l,r,k);

	up(o);

}

int query_t(int o,int l,int r){

	if(l<=t[o].l&&t[o].r<=r){

		return sum(o);

	}

	down(o); int sum=0;

	int mid=t[o].l+t[o].r>>1;

	if(l<=mid)sum+=query_t(ls(o),l,r);

	if(r>mid)sum+=query_t(rs(o),l,r);

	return sum;

}

//~~~~~~~~~~~~~~~~~~~~~~~~

struct e{

	int nxt,to;

}edge[wx*2];

void add(int from,int to){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	head[from]=num;

}

void first_dfs(int u,int fa){

	f[u]=fa;dep[u]=dep[fa]+1;

	size[u]=1;

	int maxson=-1;

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa)continue;

		first_dfs(v,u);

		size[u]+=size[v];

		if(size[v]>maxson){

			son[u]=v; maxson=size[v];

		}

	}

}

void second_dfs(int u,int topf){

	dfn[u]=++tot;

	top[u]=topf;

	tid[tot]=u;

	if(son[u]){

		second_dfs(son[u],topf);

	}

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(dfn[v]||v==son[u])continue;

		second_dfs(v,v);

	}

}

void update(int x,int y,int k){

	int fx=top[x]; int fy=top[y];

	while(fx!=fy){

		if(dep[fx]>dep[fy]){

			update_t(1,dfn[fx],dfn[x],k);

			x=f[fx];

		}

		else{

			update_t(1,dfn[fy],dfn[y],k);

			y=f[fy];

		}

		fx=top[x]; fy=top[y];

	}

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

	update_t(1,dfn[x],dfn[y],k);

	return ;

}

signed main(){

	n=read();

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

		int x,y;

		x=read(); y=read();

		x++; y++;

		add(x,y);add(y,x);

	}

	first_dfs(1,0);

	second_dfs(1,1);

	build(1,1,n);

	m=read();

	for(int i=1;i<=m;i++){

		scanf("%s",opt+1);

		if(opt[1]=='A'){

			int x,y,z;

			x=read();y=read();z=read();

			x++; y++;

			update(x,y,z);

		}

		else{

			int x; x=read(); x++;

			printf("%lld\n",query_t(1,dfn[x],dfn[x]+size[x]-1));

		}

	}

	return 0;

}

巴特西

树链剖分【洛谷P3833】 [SHOI2012]魔法树

P3833 [SHOI2012]魔法树

题目描述

输入输出格式

最新文章

热门文章