BZOJ3384 模板题【树链剖分】

题目链接

题目描述

如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z

操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

输入输出格式

输入格式：

第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。

接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）

接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

输出格式：

输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）

输入输出样例

输入样例#1：

5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

输出样例#1：

2
21

时空限制：

1s，128M

数据规模：

对于100%的数据$N≤105,M≤105 N \leq {10}^5, M \leq {10}^5 N≤105,M≤105$

---

树链剖分+线段树区间更新查询区间和

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long LL;
const int MAXN = 100000 + 5;
LL P;//MOD
int aa[MAXN];
int siz[MAXN];//子树大小包括自己
int dep[MAXN];//深度
int top[MAXN];//重链起点
int fa[MAXN];//父亲
int son[MAXN];//重链上的儿子
int num[MAXN];//线段树标号
int pre[MAXN];//num的反函数
int vis[MAXN];//标记走过
vector<int>v[MAXN];//边
LL tre[MAXN << 2];//线段树所在点的区间和
LL	add[MAXN << 2];//线段树laz
int n;//总节点数
LL ans;//树上查询的答案
int tot;//dfs序所需
void update(int t, int l, int r, int x, int y, LL k);//线段树更新
void query(int t, int l, int r, int x, int y, LL ad);//线段树查询
int dfs1(int last, int t);//第一次dfs
void dfs(int t, int ttop);//第二次dfs
void update_on_tree(int a, int b, LL z);//树上路径更新，a-b都加z
void query_on_tree(int a, int b);//树上路径查询a-b
int dfs1(int last, int t)
{
	fa[t] = last;
	dep[t] = dep[last] + 1;
	siz[t] = 1;
	vis[t] = 1;
	int I = -1;
	int maxson = 0;
	for (int i = 0; i < v[t].size(); i++)
	{
		if (vis[v[t][i]] == 0)
		{
			siz[t] += dfs1(t, v[t][i]);
			if (siz[v[t][i]] > maxson)
			{
				I = i;
				maxson = siz[v[t][i]];
			}
		}
	}
	if (I >= 0)
		son[t] = v[t][I];
	else
		son[t] = -1;
	return siz[t];
}
void dfs(int t, int ttop)
{
	top[t] = ttop;
	vis[t] = 1;
	num[t] = tot;
	pre[tot] = t;
	tot++;
	if (son[t] > 0)
		dfs(son[t], ttop);
	for (int i = 0; i < v[t].size(); i++)
	{
		if (vis[v[t][i]] == 0)
		{
			if (v[t][i] == son[t])
				continue;
			dfs(v[t][i], v[t][i]);
		}
	}
}
void update(int t, int l, int r, int x, int y, LL k)
{
	tre[t] += (min(r, y) - max(l, x) + 1)*k;
	if (l >= x && r <= y)
	{
		add[t] += k;
		return;
	}
	int mid = l + r >> 1;
	if (y <= mid)
	{
		update(t << 1, l, mid, x, y, k);
	}
	else if (x > mid)
	{
		update(t << 1 | 1, mid + 1, r, x, y, k);
	}
	else
	{
		update(t << 1, l, mid, x, y, k);
		update(t << 1 | 1, mid + 1, r, x, y, k);
	}
}
void query(int t, int l, int r, int x, int y, LL ad)
{
	if (l >= x && r <= y)
	{
		ans += tre[t];
		ans += ad * (r - l + 1);
		return;
	}
	int mid = l + r >> 1;
	if (y <= mid)
	{
		query(t << 1, l, mid, x, y, ad + add[t]);
	}
	else if (x > mid)
	{
		query(t << 1 | 1, mid + 1, r, x, y, ad + add[t]);
	}
	else
	{
		query(t << 1, l, mid, x, y, ad + add[t]);
		query(t << 1 | 1, mid + 1, r, x, y, ad + add[t]);
	}
}
void update_on_tree(int a, int b, LL z)
{
	if (dep[top[a]] < dep[top[b]])
		swap(a, b);
	if (top[a] == top[b])
	{
		a = num[a];
		b = num[b];
		if (a > b)
			swap(a, b);
		update(1, 1, n, a, b, z);
		return;
	}
	update(1, 1, n, num[top[a]], num[a], z);
	update_on_tree(fa[top[a]], b, z);
}
void query_on_tree(int a, int b)
{
	if (dep[top[a]] < dep[top[b]])
		swap(a, b);
	if (top[a] == top[b])
	{
		a = num[a];
		b = num[b];
		if (a > b)
			swap(a, b);
		query(1, 1, n, a, b, 0);
		return;
	}
	query(1, 1, n, num[top[a]], num[a], 0);
	query_on_tree(fa[top[a]], b);
	return;
}
void build(int t, int l, int r)
{
	if (l==r)
	{
		tre[t] = aa[pre[l]];
		return;
	}
	int mid = l + r >> 1;
	build(t << 1, l, mid);
	build(t << 1 | 1, mid + 1, r);
	tre[t] = tre[t << 1] + tre[t << 1 | 1];
}
int main()
{
	scanf("%d", &n);
	int m, R;
	scanf("%d%d", &m, &R);
	scanf("%d", &P);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &aa[i]);
	}
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dep[R] = 1;
	tot = 1;
	dfs1(R, R);
	memset(vis, 0, sizeof(vis));
	dfs(R, R);
	build(1, 1, n);
	for (int i = 0; i < m; i++)
	{
		int Q,x,y,z;
		ans = 0;
		scanf("%d", &Q);
		switch (Q)
		{
		case 1:
			scanf("%d%d%d", &x, &y, &z);
			update_on_tree(x, y, z);
			break;
		case 2:
			scanf("%d%d", &x, &y);
			query_on_tree(x, y);
			printf("%lld\n", ans%P);
			break;
		case 3:
			scanf("%d%d",&x,&z);
			update(1, 1, n, num[x], num[x] + siz[x] - 1, z);
			break;
		case 4:
			scanf("%d", &x);
			query(1, 1, n, num[x], num[x] + siz[x] - 1, 0);
			printf("%lld\n", ans%P);
			break;
		default:
			break;
		}
	}
}