题目链接

[HAOI2015]树上操作

数据范围：$n,m<=100000$

树剖模版题。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#define INF 0x3f3f3f3fusing namespace std;typedef long long LL;const int N = 1e5 + 10;int n, m, w[N];
int tot, id[N], nw[N];
int sz[N], dep[N], fa[N], top[N], son[N];
int idx, head[N], e[N << 1], ne[N << 1];void add(int u, int v)
{e[++ idx] = v, ne[idx] = head[u], head[u] = idx;
}void dfs1(int u, int pre, int depth)
{dep[u] =depth, fa[u] = pre, sz[u] = 1;for(int i = head[u]; i; i = ne[i]){int v = e[i];if(v == pre)	continue;dfs1(v, u, depth + 1);sz[u] += sz[v];if(sz[son[u]] < sz[v])	son[u] = v;}
}void dfs2(int u, int t)
{id[u] = ++ tot, nw[tot] = w[u], top[u] = t;if(!son[u])	return ;dfs2(son[u], t);for(int i = head[u]; i; i = ne[i]){int v = e[i];if(v == fa[u] || v == son[u])	continue;dfs2(v, v);}
}//===============================================//
struct Node
{int l, r;LL sum, add;#define ls (u << 1)#define rs (u << 1 | 1)
} tr[N * 4];void pushup(int u)
{tr[u].sum = tr[ls].sum + tr[rs].sum;
}void pushdown(int u)
{if(!tr[u].add)	return ;LL t = tr[u].add; tr[u].add = 0;tr[ls].sum += t * (tr[ls].r - tr[ls].l + 1);tr[rs].sum += t * (tr[rs].r - tr[rs].l + 1);tr[ls].add += t, tr[rs].add += t;
}void build(int u, int l, int r)
{tr[u] = {l, r, nw[l], 0};if(l == r)	return ;int mid = l + r >> 1;build(ls, l, mid), build(rs, mid + 1, r);pushup(u);
}LL query(int u, int l, int r)
{if(l <= tr[u].l && tr[u].r <= r)	return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = 0;if(l <= mid)	res += query(ls, l, r);if(r > mid)	res += query(rs, l, r);return res;
}void update(int u, int l, int r, LL v)
{if(l <= tr[u].l && tr[u].r <= r){tr[u].sum += v * (tr[u].r - tr[u].l + 1);tr[u].add += v;return ;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid)	update(ls, l ,r, v);if(r > mid)	update(rs, l, r, v);pushup(u);
}//===================================================//
LL query_path(int u, int v)
{LL res = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])	swap(u, v);res += query(1, id[top[u]], id[u]);u = fa[top[u]];}if(dep[u] < dep[v])	swap(u, v);res += query(1, id[v], id[u]);return res;
}void update_tree(int u, int k)
{update(1, id[u], id[u] + sz[u] - 1, k);
}int main()
{
#ifdef LOCALfreopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endifscanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++)	scanf("%d", &w[i]);for(int i = 1; i < n; i ++){int u, v;scanf("%d%d", &u, &v);add(u, v), add(v, u);}dfs1(1, -1, 1);dfs2(1, 1);build(1, 1, n);while(m --){int opt, x, y;scanf("%d%d", &opt, &x);if(opt == 1){scanf("%d", &y);update(1, id[x], id[x], y);}else if(opt == 2){scanf("%d", &y);update_tree(x, y);}else	printf("%lld\n", query_path(1, x));}return 0;
}

---

树上路径

数据范围：$n,m<=100000$

本题主要的难点是如何在线段树上维护区间内每个点两两相乘的和。
令$mul$代表区间内两两相乘的和，$sum$代表区间和,$ls$代表左儿子，$rs$代表右儿子。

建树时，当前区间为$u$：
$u.mul=ls.mul+rs.mul+ls.sum\ast rs.sum$。
$u.sum=ls.sum+rs.sum$

更新时(将当前区间内每一个数加$k$)：
令$len=r-l+1$
$u.mul=u.mul+C_{len}^2\ast k^2+k\ast (len-1)\ast u.sum$
$u.sum=u,sum+k\ast len$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#define INF 0x3f3f3f3fusing namespace std;typedef long long LL;const int N = 1e5 + 10, MOD = 1e9 + 7;int n, m, w[N];
int tot, id[N], nw[N];
int sz[N], fa[N], dep[N], top[N], son[N];
int idx, head[N], e[N<<1], ne[N<<1];void add(int u, int v)
{e[++ idx] = v, ne[idx] = head[u], head[u] = idx;
}void dfs1(int u, int pre, int depth)
{dep[u] = depth, fa[u] = pre, sz[u] = 1;for(int i = head[u]; i; i = ne[i]){int v = e[i];if(v == pre)	continue;dfs1(v, u, depth + 1);sz[u] += sz[v];if(sz[son[u]] < sz[v])	son[u] = v;}
}void dfs2(int u, int t)
{id[u] = ++ tot, nw[tot] = w[u], top[u] = t;if(!son[u])	return ;dfs2(son[u], t);for(int i = head[u]; i; i = ne[i]){int v = e[i];if(v == fa[u] || v == son[u])	continue;dfs2(v, v);}
}struct Node
{int l, r;LL add, mul, sum;#define ls (u << 1)#define rs (u << 1 | 1)
} tr[N * 4];void pushup(Node &u, Node L, Node R)
{u.mul = (L.mul + R.mul + L.sum * R.sum) % MOD;u.sum = (L.sum + R.sum) % MOD;
}void pushup(int u)
{pushup(tr[u], tr[ls], tr[rs]);
}void change(Node &u, LL k)
{LL len = u.r - u.l + 1;u.mul = (u.mul + len * (len - 1) / 2 % MOD * k % MOD * k % MOD + k * (len - 1) % MOD * u.sum % MOD) % MOD;u.sum = (u.sum + k * len % MOD) % MOD;u.add += k;
}void pushdown(int u)
{if(!tr[u].add)	return ;change(tr[ls], tr[u].add);change(tr[rs], tr[u].add);tr[u].add = 0;
}void build(int u, int l, int r)
{tr[u] = {l, r, 0, 0, nw[l]};if(l == r)	return ;int mid = l + r >> 1;build(ls, l, mid), build(rs, mid + 1, r);pushup(u);
}void update(int u, int l, int r, int k)
{if(l <= tr[u].l && tr[u].r <= r){change(tr[u], k);return ;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid)	update(ls, l, r, k);if(r > mid)	update(rs, l, r, k);pushup(u);
}Node query(int u, int l, int r)
{if(l <= tr[u].l && tr[u].r <= r)	return tr[u];pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(r <= mid)	return query(ls, l, r);else if(l > mid)	return query(rs, l, r);else{Node left = query(ls, l, r), right = query(rs, l, r);Node res; pushup(res, left, right);return res;}
}void update_tree(int u, int k)
{update(1, id[u], id[u] + sz[u] - 1, k);
}void update_path(int u, int v, int k)
{while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])	swap(u, v);update(1, id[top[u]], id[u], k);u = fa[top[u]];}if(dep[u] < dep[v])	swap(u, v);update(1, id[v], id[u], k);
}Node query_path(int u, int v)
{Node res = {0, 0, 0, 0, 0}, temp;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])	swap(u, v);temp = query(1, id[top[u]], id[u]);pushup(res, res, temp);u = fa[top[u]];}if(dep[u] < dep[v])	swap(u, v);temp = query(1, id[v], id[u]);pushup(res, res, temp);return res;
}int main()
{
#ifdef LOCALfreopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endifscanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++)	scanf("%d", &w[i]);for(int i = 1; i < n; i ++)	{int u, v;scanf("%d%d", &u, &v);add(u, v), add(v, u);}dfs1(1, -1, 1);dfs2(1, 1);build(1, 1, n);//query_path(2, n);while(m --){int opt, x, y, z;scanf("%d%d%d", &opt, &x, &y);if(opt == 1)	update_tree(x, y);else if(opt == 2){scanf("%d", &z);update_path(x, y, z);}else	printf("%lld\n", query_path(x, y).mul);}return 0;
}

---

软件包管理器

---

[JLOI2014]松鼠的新家

---

[LNOI2014]LCA