洛谷P3833 [SHOI2012] 魔法树

洛谷P3833 [SHOI2012] 魔法树

洛谷题目传送门

题目背景

SHOI2012 D2T3

题目描述

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

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

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：A u v d 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：Q u。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？

输入格式

第一行一个正整数 $N(1\le N\le 100000)$，表示果树的节点总数，节点以 $0,1,\dots ,N-1$ 标号，$0$ 一定代表根节点。

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

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

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

1. A u v d，表示将 $u$ 到 $v$ 的路径上的所有节点的果子数加上 $d$。保证 $0\le u,v<N,0<d<100000$

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

输出格式

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

输入输出样例 #1

输入 #1

4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2

输出 #1

3
3
2

思路讲解

首先，我们先将题目简化一下：

给定一颗树$E$，请你完成以下操作：

1. A u v d，表示将 $u$ 到 $v$ 的路径上的所有节点的点权都加上 $d$。保证 $0\le u,v<N,0<d<100000$

2. Q u，表示询问以 $u$ 为根的子树中的点权和(包括$u$本身)。

所以这道题明显是树链剖分，但我们会发现一个问题：

正常情况下我们每次访问求的是一条链$[u,v]$的权值和，而非$u$的子树，我们要想办法修改一下

先说两个很简单的定理：

1. 对于一个节点$u$，它的编号$id[u]$一定比它的所有子节点都小

2. 对于一个节点$u$，它的子树编号是连续的(中间不会混杂其他的节点)

那是不是$id[u]$后面的点都是$u$的子节点呢？显然不是。因为编号小于$id[u]$的还有可能是

$u$节点的父节点的(其他)非重儿子

我们可以用一个数组$en[u]$表示$u$的所有子节点中$id$值最大的，因为一棵子树编号是连续的。

当访问节点$u$时，我们只需要输出$[id[u],en[u]]$的区间和就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+5;
struct tre{
	ll data,l,r,lzy;
};
class Segment_tree{//线段树，我不过多赘述了
private:
	tre tree[N];ll w[N];
	void pushup(ll u){tree[u].data=tree[u*2].data+tree[u*2+1].data;}
	void add(ll u,ll v){tree[u].data+=(tree[u].r-tree[u].l+1)*v;tree[u].lzy+=v;}
	void pushdown(ll u){
		if(!tree[u].lzy)return;
		add(u*2,tree[u].lzy);add(u*2+1,tree[u].lzy);
		tree[u].lzy=0;
	}
	void build_tree(ll u,ll l,ll r){
		tree[u]=(tre){0,l,r,0};
		if(l==r){tree[u].data=w[l];return;}
		ll mid=(l+r)/2;build_tree(u*2,l,mid);build_tree(u*2+1,mid+1,r);
		pushup(u);
	}
	void change(ll u,ll x,ll y,ll v){
		ll l=tree[u].l,r=tree[u].r;
		if(l>y||r<x)return;
		if(x<=l&&r<=y){add(u,v);return;}
		pushdown(u);
		change(u*2,x,y,v);change(u*2+1,x,y,v);
		pushup(u);
	}
	ll getsum(ll u,ll x,ll y){
		ll l=tree[u].l,r=tree[u].r;
		if(l>y||r<x)return 0;
		if(x<=l&&r<=y)return tree[u].data;
		pushdown(u);
		return getsum(u*2,x,y)+getsum(u*2+1,x,y);
	}
public:
	void build_Segment_tree(ll l,ll r,ll a[]){memcpy(w,a,sizeof(w));build_tree(1,l,r);}
	void update(ll x,ll y,ll v){change(1,x,y,v);}
	ll query_sum(ll x,ll y){return getsum(1,x,y);}
};
ll h[N],to[N],ne[N],tot;
void add(ll u,ll v){tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;}
class Heavy_Chain_Decomposition{
private:
	ll fa[N],siz[N],dep[N],son[N],id[N],reid[N],top[N],en[N],tim;
	ll w[N];
//fa[u]:u的父亲节点
//siz[u]:u的子树及其大小
//dep[u]:u的深度(dep越大，u越深)
//son[u]:u的重儿子(siz最大的子节点)
//top[u]:u所在链的链头(深度最小的点)
//en[u]:u子树中的id值最大的id值(线段树中最后的点)
//id[u]:u剖分后对应的编号
//reid[i]:编号i对应节点
//w:线段树建树数组
	Segment_tree tr;
//配套线段树
	void dfs1(ll u,ll fath,ll dp){
//第一次深搜：求出fa,siz,dep,son
//u:当前节点,fath:父亲节点,dp:深度
		dep[u]=dp;fa[u]=fath;siz[u]=1;
//更新fa,siz,dep
		for(ll i=h[u];i;i=ne[i]){
			ll v=to[i];if(v==fath)continue;//不能跑回去
			dfs1(v,u,dp+1);siz[u]+=siz[v];//自下而上更新siz[u]
			if(siz[v]>siz[son[u]])son[u]=v;//找出重儿子
		}
	}
	void dfs2(ll u,ll fath,ll ori){
//第二次深搜：求出id,reid,top
//u:当前节点,fath:父节点,ori:当前链的链头
		id[u]=++tim;reid[id[u]]=u;top[u]=ori;en[u]=id[u];
//依照访问顺序更新id,reid,更新top,en初值为id[u]
		if(son[u]){dfs2(son[u],u,ori);en[u]=max(en[u],en[son[u]]);}
//剖出重链(有重儿子先访问重儿子),记得要更新en[u]
		for(ll i=h[u];i;i=ne[i]){
			ll v=to[i];if(v==fath||v==son[u])continue;
			dfs2(v,u,v);en[u]=max(en[u],en[v]);//新建一条重链,同时更新en[u];
		}
	}
public:
	void build(ll en,ll a[]){
//建树
		dfs1(1,0,1);dfs2(1,0,1);
		for(ll i=1;i<=en;i++)w[id[i]]=a[i];
		tr.build_Segment_tree(1,en,w);
	}
	void change(ll x,ll y,ll v){
//将链[x,y]上的点权都加v
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			tr.update(id[top[x]],id[x],v);
			x=fa[top[x]];
		}
		if(id[x]>id[y])swap(x,y);
		tr.update(id[x],id[y],v);
	}
	ll query(ll x){return tr.query_sum(id[x],en[x]);}
//查询x的子树的点权和
}tr;
ll n,a[N],m;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(ll i=1;i<=n-1;i++){
		ll x,y;cin>>x>>y;x++;y++;add(x,y);add(y,x);
	}
	tr.build(n,a);
	cin>>m;
	for(ll i=1;i<=m;i++){
		char xx;
		cin>>xx;
		if(xx=='A'){
			ll x,y,z;cin>>x>>y>>z;x++,y++;tr.change(x,y,z);
		}
		else {
			ll x;cin>>x;x++;cout<<tr.query(x)<<'\n';
		}
	}
	return 0;
}

总结

我们要灵活应用树链剖分中的种种性质，不能死读书，读死书