树链剖分模板

#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 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);//线段树查询
void build(int t, int l, int r);//用初值建线段树
int dfs1(int last, int t);//第一次dfs得到fa dep siz son
void dfs(int t, int ttop);//第二次dfs得到num pre top
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 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];
}
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;
}
int main()
{
	int m;
	scanf("%d%d", &n,&m);//n个点m个操作
	for (int i = 1; i <= n; i++)//输入树结点的初始值
	{
		scanf("%lld", &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);
	}
	int root = 1;//根为1
	dep[root] = 1;
	tot = 1;
	dfs1(root, root);
	memset(vis, 0, sizeof(vis));
	dfs(root, root);
	for (int i = 0; i < m; i++)
	{
		int Q,x,y,z;
		ans = 0;
		scanf("%d", &Q);
		switch (Q)
		{
		case 1://x到y路径上的结点都加z
			scanf("%d%d%d", &x, &y, &z);
			update_on_tree(x, y, z);
			break;
		case 2://求x到y路径上的结点和
			scanf("%d%d", &x, &y);
			query_on_tree(x, y);
			printf("%lld\n", ans);
			break;
		case 3://以x为根的子树所有节点都加z
			scanf("%d%d",&x,&z);
			update(1, 1, n, num[x], num[x] + siz[x] - 1, z);
			break;
		case 4://求以x为根的子树所有结点之和
			scanf("%d", &x);
			query(1, 1, n, num[x], num[x] + siz[x] - 1, 0);
			printf("%lld\n", ans);
			break;
		default:
			break;
		}
	}
}